AtCoder Regular Contest 050 C - LCM 111

問題

　を個並べてできる整数を、個並べてできる整数をとしたとき、との最小公倍数をで割った余りを求めよ。

解法

　を個並べてできる整数をとしたときであることがわかる。最小公倍数はであるので、をで割った余りが求まれば良い。とする。ここでは「が個、が1個」という整数を個並べてできる整数である。

　例. のとき、であり、

　結局はそれぞれ「ある整数をある回数並べてできる整数」という形で表現できる。これをで割った余りは並べる回数をとしたときダブリングによってで求めることができるので、それぞれ個別に余りを求めた後掛け合わせて最後にで割った余りを取ればこの問題が解ける。

反省

　51分31秒(0WA)でAC。久しぶりにしっかりと考察して自力で解けたという感じだったが、おそらくこれもコンテストに当時参加していたようなので解説スライドをチラ見したことがあるのだろう。2年半前のコンテストらしいのではっきりと記憶に残っているわけではないが、何となくの方向性などはどこか覚えていて考察が変な方向にいかないというくらいの影響はありそうだ。

　あまりコンテストは休んでないはずなのでここから先は一応見たことがある問題が多いのではないか。B問題で詰まってC問題まで読んでないということはいくらかありそうだが。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

ll A, B, M;

ll MODpow(ll n, ll m) {
    ll result = 1;
    while (m) {
        if (m % 2 == 1) {
            result *= n;
            result %= M;
        }

        m /= 2;
        n *= n;
        n %= M;
    }

    return result;
}

ll f(ll n, ll c) {
    //「0がc - 1個,1が1個」をn回繰り返し並べた数を返す
    ll result = 0;
    ll m = 1;
    ll d = c;
    while (n) {
        if (n & 1) {
            result *= MODpow(10, d);
            result += m;
            result %= M;
        }

        m = m * MODpow(10, d) + m;
        m %= M;
        d *= 2;
        n /= 2;
    }
    return result;
}

ll gcd(ll a, ll b) {
    return (b ? gcd(b, a % b) : a);
}

int main() {
    cin >> A >> B >> M;
    if (A < B) {
        swap(A, B);
    }

    ll g = gcd(A, B);
    cout << f(A, 1) * f(B / g, g) % M << endl;
}