Tile Covering

Suppose tiles of length $B$ are used $x$ times. Since the two lengths alternate and both the first and last tiles have length $A$, tiles of length $A$ are used $x+1$ times. Both tile lengths must be used, so $x\geq1$.

Therefore,

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

Temporarily ignore the condition $A\neq B$. Let $S=A+B$. Then

$$N=Sx+A.$$

Once $S$ with $1\leq S\leq N$ is fixed, division with remainder uniquely determines $x$ and $A$, and therefore also $B=S-A$. Thus, we initially have choices for .

Now remove the invalid cases.

First, consider $A=0$. This happens exactly when the remainder of dividing $N$ by $S$ is zero, so it is equivalent to $S$ being a divisor of $N$.

Second, consider $A=B$. In this case,

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

Since $S=2A$,

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

If $S$ divides $N$, then $\frac{2N}{S}$ is even. In the case $A=B$, is odd. Therefore, these two kinds of invalid cases are disjoint.

Also, every positive divisor $S$ of $2N$ except $2N$ itself satisfies $S\leq N$. If $\frac{2N}{S}$ is even, then divides , corresponding to . If it is odd, it corresponds to . Hence the number of invalid choices is the number of positive divisors of , excluding itself.

Let $D(M)$ denote the number of positive divisors of $M$. The answer is

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

We can compute $D(2N)$ by testing divisors up to $\sqrt{2N}$, giving an $O(\sqrt N)$ algorithm.

Since the answer is $N-D(2N)+1 \leq N \leq 10^{10}$, it always fits in a signed 64-bit integer.

Solution written by GPT5.6