ARC050 C - LCM 111

問題文

http://arc050.contest.atcoder.jp/tasks/arc050_c

解法

1 が A 桁続いたものと，1 が B 桁続いたものの最大公約数 G は，1 が gcd(A, B) 桁続いたものになる．
例えば 111111 (A = 6) と 1111 (B = 4) の最大公約数は，1 が gcd(6, 4) = 2桁続いたもの．
これは，
111111 = 1111 * 100 + 11
11 = 11 * 1 + 0
のようにユークリッド互除法を適用していくと，1 が並んだものがどんどん小さくなっていく．この桁数が，gcd(A, B) に対応する．

あとは A * B / G を考えるだけなので，A，B / G がどうなるか考えば十分．
ここで 1 が並んだ数は
a(k+1) = 10a(k) + 1, a(1) = 1
つまり
a(k+2) = 11a(k+1) - 10a(k)
となる数列と考えられるので，これは行列累乗で求められる．これで A は求まった．

次に，B / G を考える．これは 1000100010001...1 のような形をしていることがわかる．1 が現れる間隔が，G に対応しているので，これは
b(k+1) = 10^G b(k) + 1， b(1) = 1
という数列，つまり
b(k+2) = (10^G + 1)b(k+1) - 10^G b(k)
という数列で表される．
B はこれの B / D 項なので，同様に行列累乗で求める．

ソースコード

#include <bits/stdc++.h>
using namespace std;

// matrix は長いので略

int main() {
    ll A, B, M;
    cin >> A >> B >> M;
 
    ll g = __gcd(A, B);
    vector<ll> b1 = {11, 1};
    vector<ll> b2(2);
    b2[0] = modpow(10, g, M) + 1;
    b2[1] = 1;
    auto C = make_matrix<ll>(2, 2);
    C[0][0] = 11; C[0][1] = -10 + M;
    C[1][0] = 1;
    C = modpow(C, A - 1, M);
    auto C2 = make_matrix<ll>(2, 2);
    C2[0][0] = modpow(10, g, M) + 1;
    C2[0][1] = -modpow(10, g, M) + M;
    C2[1][0] = 1;
    C2 = modpow(C2, B / g - 1, M);
    
    ll x = modmul(C, b1, M)[1];
    ll y = modmul(C2, b2, M)[1];
    cout << (x * y) % M << endl;
}

感想

行列累乗じゃないコードのほうがスッキリしてた．
1111 ... を等比数列みたいに捉えるのに時間がかかってしまった．