【ABC174】C - Repsept

atcoder.jp

解法

Kの倍数かどうかがわかればよいので、 は mod Kで考えてよい。
さらに、 という数列を順に調べることをK+1回繰り返せば、鳩ノ巣原理で必ずループが始まる。
そのため、 という数列を順に調べることをK回繰り返して、その中にKの倍数があれば何回目かを出力、なければ-1を出力すればよい。

実装

10ⁱを計算するときは、繰り返し2乗法を使わないと間に合わない。

long long modpow(long long a, long long n, long long k) {
    if (n == 0) return 1;
        auto t = modpow(a, n / 2, k) % k;
        t = t * t % k;
        if (n & 1) t = t * a % k;
        return t;
}

void solve(long long K){
    vector<long long> k(K+1, 0);
    REP (i, K) {
        k[i+1] = (k[i] + modpow(10LL, i, K) * 7) % K;
        if (!k[i+1]) {
            cout << i+1 << endl;
            return;
        }
    }
    cout << -1 << endl;
}