BOJ 26395 - Iksevi
타일의 길이를 $2k$라 하자.
일반성을 잃지않고 마름모 꼭짓점 위쪽에 점이 있다고 할 때 그 좌표는 $(2ak, (2b+1)k)$ 이다.
$x$ 좌표는 $k$에 짝수가 곱해졌고 $y$ 좌표는 $k$에 홀수가 곱해졌다.
어쨌든 여기서 $gcd(x,y)$ 의 약수들 중 $k$ 후보를 뽑을 수 있고 여기까지의 아이디어로 Subtask 2까지 해결할 수 있다.
Subtask 3을 해결하기 위해 가능한 $k$의 후보를 빠르게 세는 방법은 다음과 같다.
$g=gcd(x,y)$ 라 한다면 $x'=\dfrac{x}{g},\ y'=\dfrac{y}{g}$ 이고 $k$의 후보는 $g$의 약수이다.
그럼 $\dfrac{x}{k}$와 $\dfrac{y}{k}$ 의 parity는 다르다.
어떤 후보를 $h$라고 하면 $h \mid g$ 이므로 $\dfrac{x}{k}=hx', ~ \dfrac{y}{k}=hy'$ 이다.
$x', y'$ 의 parity가 같다면 둘에 동일한 수를 곱해도 parity가 변하지 않는다.
다르다면 홀수를 곱해야 parity가 다른체로 유지된다.
따라서 $h$는 홀수여야 함을 알 수 있고 $g$의 불가능한 경우들을 배제하고 약수중 홀수인 약수의 개수를 세는것이 결국 정답이다.
이를 에라토스테네스의 체로 셀 수 있다.
Comments