AtCoder ARC 050 C - LCM 111 (試験管黄色)

レピュニット数を題材とした問題。

• 問題へのリンク

問題概要

を 個並べた数と、 を 個並べた数の最小公倍数を で割ったあまりを求めよ。

制約

• 
• 

考えたこと

を並べた数をレピュニット数とよぶ。数学的に面白い性質が色々ある。

レピュニット数の最大公約数は、実は を 個並べた数になる。このことを Euclid の互助法に基づいて検証する。

たとえば ( が 個) と、 ( が 個) の最大公約数を求めたいとする。

であり、 と は互いに素なので、

になると言える。一般に、 のとき、

が成立する。この の部分の変化が Euclid の互助法における変化に他ならない。よって、上に述べたことが成立する。

最小公倍数を求める

を 個並べた数を と表すことにすると、求めたい数は として、

ということになる。 が素数とは限らないので、 で割るという演算は回避したい。そこで、

• 
• 

であることに着目してこれを求めることにする。

全体として、計算量は となる。

コード

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

// a^n mod m
long long pow(long long a, long long n, long long m) {
    if (n == 0) return 1;
    long long t = pow(a, n/2, m);
    t = t * t % m;
    if (n & 1) t = t * a % m;
    return t;
}

// 1 + a + ... + a^{n-1} mod m
long long ser(long long a, long long n, long long m) {
    if (n == 0) return 0;
    long long res = ser(a * a % m, n/2, m);
    res = res * (a + 1) % m;
    if (n & 1) res = (res * a + 1) % m;
    return res;
}

int main() {
    long long A, B, M;
    cin >> A >> B >> M;

    long long G = gcd(A, B);
    long long fA = ser(10, A, M);
    long long fBdivfG = ser(pow(10, G, M), B/G, M);
    cout << fA * fBdivfG % M << endl;
}