AtCoder Regular Contest 050 C - LCM 111
C: LCM 111 - AtCoder Regular Contest 050 | AtCoder
解法
lcm(x,y)=xy/gcd(x,y) が使えそうなので、 gcd(111...., 111....) の性質について調べてみることにする。
まず以下の等式が成り立つ。
$$ \gcd(111111111, 111) = \gcd(111111000, 111) $$
これはユークリッドの互除法、
$$ \gcd(a,b) = \gcd(a-b,b) $$
から分かる。
次に次の等式が成り立つ。
$$ \gcd(111111000, 111) = \gcd(111111 \cdot 1000, 111) = \gcd(111111, 111) $$
これは 1111.... は 2 と 5 を素因数として持たないので 10000... とは互いに素だからである。
この 2 つの等式から次のような式変形ができる。
$$ \begin{align} \gcd(111111111, 111) &= \gcd(111111000, 111) \\ &= \gcd(111111, 111) \\ &= \gcd(111000, 111) \\ &= \gcd(111,111) \\ &= \gcd(0,111) \\ &= 111 \end{align} $$
もう一つ例を示す。今回は 0 のカットをを省略する。 $$ \begin{align} \gcd(1111111,11111) &= \gcd(11,11111) \\ &= \gcd(11,111) \\ &= \gcd(11,1) \\ &= \gcd(1,1) \\ &= \gcd(0,1) \\ &= 1 \end{align} $$
この例で 1 の個数に着目してみよう。
$$ \begin{align} \gcd(7,5) &= \gcd(2,5) \\ &= \gcd(2,3) \\ &= \gcd(2,1) \\ &= \gcd(1,1) \\ &= \gcd(0,1) \\ &= 1 \end{align} $$
この例を見ればわかる通り、
- gcd(1 が a 個続く、1 が b 個続く) = 1 が gcd(a,b) 個続く
が成り立つ。
たとえば a=9, b=3 だった場合、$111111111 \cdot 111 / 111$ を計算すればいい。しかし今回は逆元が使えないため、割り算を逆元で処理することはできない。
逆元が使えないので、 $(111111111/111)\cdot 111 = 001001001 \cdot 111$ を計算することにしよう。
001001001... を mod m で求めるには、等比数列の和を mod m で求められればいい。等比数列の和は有名な公式があるが、あれは逆元が必要になので根本的解決にならない。そのため、別の方法を取る必要がある。2 通りの方法を説明する。
等比数列の和をダブリングで求める方法
発想は累乗を O(log n) で計算する方法に近い。
(1) n が奇数 $$ 1+a+\cdots+a^{n-1}=1+a\cdot(1+a+\cdots a^{n-2}) $$
(2) n が偶数 $$ 1+a+\cdots+a^{n-1}=(1+a+\cdots + a^{n/2 -1})+a^{n/2}(1+a+\cdots + a^{n/2 -1}) $$
で計算できる。
要は $f(n)=1+a+\cdots + a^{n-1}$ としたとき、$f(n)$ は次のように計算できる。
$$ f(n)=\begin{cases} 1+f(n-1)\cdot a & \text{n が奇数} \\ f(n/2)+a^{n/2}f(n/2) \cdot & \text{n が偶数} \end{cases} $$
等比数列の和を行列累乗で求める方法
総和を求めるには行列累乗を使う方法もある。こちらは一般の定数係数線形漸化式に対して適用可能なので覚えておくと良いかもしれない。
$a_n = ra_{n-1} $ で表せる数列を考えよう。$S_n = a_0+a_1+\cdots + a_{n-1}$ とすると $a_n$ と $S_n$ は次のように表せる。
$$ \begin{bmatrix} a_{n+1} \\ S_{n+1} \end{bmatrix}=\begin{bmatrix} r & 0 \\ 1 & 1 \end{bmatrix}\begin{bmatrix} a_{n} \\ S_{n} \end{bmatrix} $$
つまり
$$ \begin{bmatrix} a_{n} \\ S_{n} \end{bmatrix}=\begin{bmatrix} r & 0 \\ 1 & 1 \end{bmatrix}^n\begin{bmatrix} a_{0} \\ S_{0} \end{bmatrix} $$
である。
