B - A^B^C

atcoder.jp

1の位の周期性を考える。 B^Cは繰り返し二乗法で求めて、周期の長さで割れば良い。 周期の中でどの位置にあるのかを求めるのが少し苦戦してしまった。

例えば、3 の周期は「3 9 7 1」の長さ4であり、3⁹ の場合は周期により、1となる。単純に 9 % 3 すると 0 になるので、インデックスがズレてしまう。算出するにはどうすればよいのか分かるのに時間がかかった。 最終的には (n % len + len-1) % len とすれば良いことがわかった。

解説では、単純に周期は4になること、繰り返し二乗法で乗数が十分小さくなるので単純に掛けても良いので、もう少しシンプルに回答できることを知った。 これに周期が4であると考えれば良いことに気がつくのは結構難しそうだが、繰り返し二乗法で十分小さくなることには気づきたかった。

long long power_mod(long long n, long long k, long long mod) {
    long long result = 1;
    // k を右シフトしつつ n を 2 乗していく
    while (k > 0) {
        // k の最下ビットが 1 なら、今の n を答えに掛ける
        if ((k & 1) == 1) result = (result * n) % mod;
        n = n * n % mod;
        k >>= 1;
    }
    return result;
}


void solve(long long A, long long B, long long C){
    vl cnt;
    map<ll,ll> memo;
    ll wk = 1;
    REP(i, 100) {
        wk *= A;
        wk %= 10;
        if (memo[wk]) break;
        memo[wk] = 1;
        cnt.push_back(wk);
    }

    ll len = memo.size();
    ll n = power_mod(B, C, len);
    ll i = (n % len + len-1) % len;
    cout << cnt[i] << endl;
}