No.050 C

まずは $x, y$ の最大公約数を求める. これはユークリッドの互除法をシミュレートすると, 1を $C = \gcd(A, B)$ 個並べたものとなる. これを $z$ とすると, 最小公倍数は $xy/z$ となる.

$M$ は素数に限定されていないので, 逆元は使えない.

そこで, $x/z$ を考えると, これは 00..01 と0を $C-1$ 個並べて最後に1を追加したものを $A/C$ 個並べたものとなる.

00..01 のように $i-1$ 個の0と1個の1を並べたものを $j$ 個並べた数を $A(i, j)$ とすると,

$$A(i, j) = \begin{cases} A(i, j-1) * 10^i + A(i, 1) & (j \equiv 1 \pmod 2) A(i, j/2) * 10^{ij/2} + A(i, j/2) & (j \equiv 0 \pmod 2) \end{cases}$$

のように計算できるので, これで $\log$ のスケールで計算できるようになる.