Concatenate and Divide

$d(A)$를 양의 정수 $A$의 십진수 자릿수라고 하자. 그러면

$$A@B=A\cdot 10^{d(B)}+B$$

이므로, $A@B$가 $B$로 나누어떨어질 조건은

$$B \mid A\cdot 10^{d(B)}$$

와 같다.

$g=\gcd(X,Y)$라 하고 $X=ga$, $Y=gb$라고 쓰자. 그러면 $\gcd(a,b)=1$이고 $X<Y$이므로 $a<b$이다. 두 조건은 각각

$$gb \mid ga\cdot 10^{d(Y)},\qquad ga \mid gb\cdot 10^{d(X)}$$

이고, $g$를 약분하면

$$b \mid a\cdot 10^{d(Y)},\qquad a \mid b\cdot 10^{d(X)}$$

이다. $\gcd(a,b)=1$이므로 이는

$$b \mid 10^{d(Y)},\qquad a \mid 10^{d(X)}$$

와 동치이다.

따라서 $d(X),d(Y)$를 고정하면, $a$는 $10^{d(X)}$의 약수, $b$는 $10^{d(Y)}$의 약수 중에서 고르면 된다. 또한 $\gcd(a,b)=1$과 $a<b$를 만족해야 한다.

이제 고정된 $d_X=d(X)$, $d_Y=d(Y)$, $a$, $b$에 대해 가능한 $g$의 범위를 세자. $X=ga$, $Y=gb$가 각각 자릿수 $d_X$, $d_Y$를 가져야 하므로

$$10^{d_X-1} \leq ga \leq \min(N,10^{d_X}-1),$$ $$10^{d_Y-1} \leq gb \leq \min(N,10^{d_Y}-1)$$

이어야 한다. 따라서

$$L=\max\left(\left\lceil\frac{10^{d_X-1}}{a}\right\rceil,\left\lceil\frac{10^{d_Y-1}}{b}\right\rceil\right),$$ $$R=\min\left(\left\lfloor\frac{\min(N,10^{d_X}-1)}{a}\right\rfloor,\left\lfloor\frac{\min(N,10^{d_Y}-1)}{b}\right\rfloor\right)$$

이다. $L \leq g \leq R$인 정수 $g$의 개수는 $\max(0,R-L+1)$이다.

$N \leq 10^{18}$이므로 가능한 자릿수는 최대 $19$개이다. 각 $d$에 대해 $10^d$의 약수는 $2^i5^j$ 꼴이며 $0 \leq i,j \leq d$이다. 따라서 모든 $d_X,d_Y,a,b$를 직접 순회해도 충분히 빠르다.

Solution written by GPT5.5