Tile Covering

길이가 $B$인 타일이 $x$번 사용되었다고 하자. 처음과 마지막 타일이 모두 길이 $A$이고 두 종류의 타일을 번갈아 놓으므로 길이 $A$인 타일은 $x+1$번 사용된다. 두 종류의 타일을 모두 사용해야 하므로 $x\geq1$이다.

따라서

$$A(x+1)+Bx=(A+B)x+A=N$$

이 성립한다.

먼저 $A\neq B$ 조건을 잠시 제거한다. $S=A+B$라 하자. 위 식은

$$N=Sx+A$$

가 된다. $1\leq S\leq N$을 하나 고정하면 나눗셈의 몫과 나머지에 의해 $x$와 $A$가 유일하게 정해지고, 따라서 $B=S-A$도 유일하게 정해진다. 그러므로 처음에는 $S=1,2,\cdots,N$의 $N$가지 경우를 생각할 수 있다.

이 중 올바르지 않은 경우를 제거하자.

첫째, $A=0$인 경우이다. 이는 $N$을 $S$로 나눈 나머지가 $0$인 경우이므로 $S$가 $N$의 약수인 경우와 정확히 같다.

둘째, $A=B$인 경우이다. 이때

$$N=(2x+1)A$$

이고 $S=2A$이므로

$$2N=(2x+1)S$$

이다.

$S$가 $N$의 약수이면 $\frac{2N}{S}$는 짝수이다. 반대로 $A=B$인 경우에는 $\frac{2N}{S}=2x+1$이 홀수이다. 따라서 두 종류의 잘못된 경우는 서로 겹치지 않는다.

또한 $2N$의 양의 약수 $S$ 중 $S\neq2N$인 것은 모두 $S\leq N$이다. 이때 $\frac{2N}{S}$가 짝수이면 $S$는 $N$의 약수이므로 $A=0$인 경우이고, 홀수이면 $A=B$인 경우이다. 즉, 제거해야 하는 경우의 수는 $2N$의 양의 약수 개수에서 $2N$ 자체를 제외한 값이다.

$D(M)$을 $M$의 양의 약수 개수라 하면 정답은

$$N-D(2N)+1$$

이다.

$D(2N)$은 $1$부터 $\sqrt{2N}$까지 나누어 보면서 $O(\sqrt N)$에 구할 수 있다.

정답은 $N-D(2N)+1 \leq N \leq 10^{10}$이므로 항상 부호 있는 $64$비트 정수 범위에 들어간다.

Solution written by GPT5.6