# ARC050 C - LCM111

## 問題リンク
- https://atcoder.jp/contests/arc050/tasks/arc050_c

## 解法
### 整理
まず, $1$を$A$個並べた数は $1+10+10^2+\cdots+10^{A-1} =\frac{10^A-1}{9}$ と書ける.
同様に, $1$を$B$個並べた数は$1+10+10^2+\cdots+10^{B-1}=\frac{10^B-1}{9}$ と書ける.
したがって, 求めるべきは $$\mathrm{lcm}\left(\frac{10^A-1}{9},\frac{10^B-1}{9}\right) \bmod M$$ となる.

そのまま扱うのは大変そうなので, ある程度式変形を行う.

$$
\begin{aligned}
\mathrm{lcm}\left(\frac{10^A-1}{9},\frac{10^B-1}{9}\right)&=\frac{\mathrm{lcm}\left(10^A-1,10^B-1\right)}{9}\\
&=\frac{\left(10^A-1\right)\left(10^B-1\right)}{9\cdot\gcd\left(10^A-1,10^B-1\right)}
\end{aligned}$$

$\gcd(10^A-1,10^B-1)$ について考えよう.

非負整数 $n,m$ に対して $f(n,m)$ を $f(n,m)=\gcd(10^n-1,10^m-1)$ で定める.

$f(n,m)=f(m,n)$ より $n\leq m$ として考えてよく, このとき, 等式$\gcd(x,y)=\gcd(x,y-x)$から

$$
\begin{aligned}
f(n,m)
&=\gcd(10^n-1,10^m-1) \\
&=\gcd(10^n-1,10^m-10^n)\\
&=\gcd(10^n-1,10^n(10^{m-n}-1))
\end{aligned}
$$

となる.
ここで, $10^n$ と $10^n-1$ は隣り合う整数だから互いに素. よって

$$
\begin{aligned}
\gcd(10^n-1,10^n(10^{m-n}-1))
&=\gcd(10^n-1,10^{m-n}-1)\\
&=f(n,m-n)
\end{aligned}
$$

となる. これを繰り返し用いると, 以下が得られる

$$f(n,m)=f(n,m \bmod n)$$

よって, $$f(n,m)=10^{\gcd(n,m)}-1$$ が成り立つ(Euclid互除法を思い出すとよい).

これにより, 求めるべきは $g=\gcd(A,B)$ として

$$
\frac{\left(10^A-1\right)\left(10^B-1\right)}{9\cdot\left(10^{g}-1\right)} \bmod M
$$

と表せる.

### 計算
上の式をそのまま計算してもACは得られない. なぜならば, $M$ は合成数である可能性があり, その場合 $9(10^{g}-1)$ が $\bmod M$ で逆元を持つと限らないから.

ここで, $g$ が $B$ を割り切ることに着目する. すると以下の式変形が行える.

$$\frac{\left(10^A-1\right)\left(10^B-1\right)}{9\cdot(10^{g}-1)}=\frac{10^A-1}{10-1}\times\frac{\left(10^{g}\right)^{\frac{B}{g}}-1}{10^g-1}$$

いずれも $\frac{\alpha^k-1}{\alpha-1}$ という形だから, この値の $\bmod M$ を高速に求めることができればよい.

$$\frac{\alpha^k-1}{\alpha-1}=1+\alpha+\alpha^2+\cdots+\alpha^{k-1}$$ であるから, $s_i=\frac{\alpha^i-1}{\alpha-1}=1+\alpha+\alpha^2+\cdots+\alpha^{i-1}$ とすると漸化式 $s_{i+1}=\alpha s_i+1$ が成り立つ. これを行列を用いて表すと以下のようになる.

$$
\begin{pmatrix}
s_{i+1} \\
1
\end{pmatrix}
= \begin{pmatrix}
\alpha & 1 \\
0 & 1
\end{pmatrix}\begin{pmatrix}
s_i\\
1
\end{pmatrix}
$$

繰り返し用いて

$$
\begin{pmatrix}
s_{k} \\
1
\end{pmatrix}
= \begin{pmatrix}
\alpha & 1 \\
0 & 1
\end{pmatrix}^{k}\begin{pmatrix}
s_0\\
1
\end{pmatrix}
$$

$s_0=1$ であり, $\begin{pmatrix}
\alpha & 1 \\
0 & 1
\end{pmatrix}^{k}$ は繰り返し二乗法を用いれば $O(\log k)$ timeで計算可能. また, この計算は逆元を必要としていない. よって $\bmod M$ での逆元の存在を利用することなく $s_k$ の値を $O(\log k)$ timeで求めることができた.
これを用いると

$$\frac{10^A-1}{10-1},\frac{\left(10^{g}\right)^{\frac{B}{g}}-1}{10^g-1}$$

いずれも $O(\log \max(A,B))$ timeで計算可能. したがってこの問題を $O(\log \max(A,B))$ timeで解くことができた.

### 提出
- https://atcoder.jp/contests/arc050/submissions/54210716