AtCoder Regular Contest 050 C - LCM 111

C - LCM 111

問題概要

1をA個並べた数と1をB個並べた数の最小公倍数をMで割った数を求めよ．

$ A,B \le 10^{18} $ $ 2 \le M \le 10^9 $

解法概要

公式解説にならい，1を$ n$個並べた数を$ \mathit{one}(n)$とする． また，以下のメモでは$ M$で割った剰余を求める計算は省略する．

$ \mathit{lcm}(\mathit{one}(A), \mathit{one}(B)) = \frac{\mathit{one}(A)\mathit{one}(B)}{\mathit{gcd}(\mathit{one}(A), \mathit{one}(B))}$なので，まずは$ \mathit{gcd}(\mathit{one}(A), \mathit{one}(B))$を求めたい．

ユークリッドの互除法より $ \mathit{gcd}(\mathit{one}(A), \mathit{one}(B)) = \mathit{gcd}(\mathit{one}(B), \mathit{one}(A)\% \mathit{one}(B)) = \mathit{gcd}(\mathit{one}(B), \mathit{one}(A \% B))$

なぜならば，$ A = B \times p + q $ とすると $ \mathit{one}(A) \% \mathit{one}(B)$ $ = \mathit{one}(B \times p + q) \% \mathit{one}(B) = (\mathit{one}(B \times p) \% \mathit{one}(B) + \mathit{one}(q) \% \mathit{one}(B)) \% \mathit{one}(B) $ $ = \mathit{one}(q) \% \mathit{one}(B) = \mathit{one}(q) = \mathit{one}(A \% B)$ したがって$ \mathit{gcd}(\mathit{one}(A), \mathit{one}(B)) = \mathit{one}(\mathit{gcd}(A, B))$

求めるべき最小公倍数は $ \mathit{lcm}(\mathit{one}(A), \mathit{one}(B)) = \frac{\mathit{one}(A)\mathit{one}(B)}{\mathit{one}(\mathit{gcd}(A, B))}$

ここで， $ one(A)$は$ a_1 = 1,\ a_{k+1}=10a_k+1$としたときの第$ A$項， $ \frac{\mathit{one}(B)}{\mathit{one}(\mathit{gcd}(A, B))}$は$ b_1=1, b_{k+1}=10^{\mathit{gcd}(A,B)}b_k + 1$としたときの第$ \frac{B}{\mathit{gcd}(A, B)}$項なので， それぞれ行列累乗で計算すれば間に合う．

具体的には以下のような行列式が作れる．

ソースコード

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

ll gcd(ll a, ll b){
    if(b == 0) return a;
    else return gcd(b, a%b);
}

vector< vector<ll> > product(vector< vector<ll> > A, vector< vector<ll> > B, ll m){
    int height = A.size(), width = B[0].size(), n = B.size();
    
    vector< vector<ll> > C(height, vector<ll>(width, 0));
    
    for(int i=0;i<height;++i){
        for(int j=0;j<width;++j){
            for(int k=0;k<n;++k){
                C[i][j] += (A[i][k] * B[k][j]) % m;
                C[i][j] %= m;
            }
        }
    }
    
    return C;
}

vector< vector<ll> > matrix_pow(vector< vector<ll> > A, ll t, ll m) {
    int n = A.size();
    vector< vector<ll> > B(n, vector<ll>(n, 0));
    for(int i=0;i<n;++i) B[i][i] = 1;
    while(t){
        if(t & 1){
            B = product(B, A, m);
        }
        A = product(A, A, m);
        t >>= 1;
    }
    return B;
}

ll calc_a(ll a, ll m) {
    vector< vector<ll> > A(2, vector<ll>(2, 0));
    A[0][0] = 10; A[0][1] = 1; A[1][1] = 1;
    vector< vector<ll> > B(2, vector<ll>(1, 1));
    vector< vector<ll> > C = product(matrix_pow(A, a-1, m), B, m);
    return C[0][0] % m;
}

ll mypow(ll a, ll t, ll m) {
    ll ret = 1LL;
    while(t){
        if(t & 1){
            ret *= a;
            ret %= m;
        }
        a *= a;
        a %= m;
        t >>= 1;
    }
    return ret;
}

ll calc_b(ll b, ll g, ll m) {
    ll p = mypow(10LL, g, m);
    vector< vector<ll> > A(2, vector<ll>(2, 0));
    A[0][0] = p; A[0][1] = 1; A[1][1] = 1;
    vector< vector<ll> > B(2, vector<ll>(1, 1));
    vector< vector<ll> > C = product(matrix_pow(A, b/g-1, m), B, m);
    return C[0][0] % m;
}

int main() {
    ll a,b,m;
    cin >> a >> b >> m;

    ll g = gcd(a, b);

    ll lcm = (calc_a(a, m) * calc_b(b, g, m)) % m;
    cout << lcm << endl;
}

所感

整数の問題のこれぐらいの重さの考察はできるようになりたい． てか後2分でCADDiコンだけどレジってないやばい