AtCode ARC113 -B A^B^C 解

##問題概要
正整数A,B,Cに対して$A^{B^C}$の1の位を求めよ。

• 制約
  • $1 \le A,B,C \le 10^9$

https://atcoder.jp/contests/arc113/tasks/arc113_b
##考察
愚直解では間に合わないので計算量を落とす。

$A^{B^C}$ の1の位とは$A^{B^C}$ のmod10での値のこと。
Aは1桁目しか興味がないので初めからA %= 10としてよい。これでもまだ間に合わないので$B^C$の桁も落としたい。

10は素数ではないので、フェルマーの小定理によってnestされた累乗を計算することはできない。そこで、Aのmod10での周期p(必ず10以下になる)を使って、$B^C$の桁を落とすことを考える。

$B^C$のA(mod10)-周期成分は除いてよいので、$B^C$をpower = pow_mod(b,c,p)に代えてよい。このpowerは周期p以下になるので、以降の計算量は極小で済む。

周期pはループを回して強引に求めてしまえばよい。今回のケースでは、どうせ10回(=modの値)もかからないので。

##実装

int main() {
    const int mod = 10;
    // read input
    auto a = in<ull>() % mod;
    auto b = in<ull>();
    auto c = in<ull>();

    // trivial case: mod period = 1
    // e.g., 5*5 = 5 mod10
    if (a <= 1 || a == 5 || a == 6) {
        print(a);
        return 0;
    }

    // calc non-trivial mod period of a.
	// d is a temporary variable
    ll d      = (a * a) % mod;
    ll period = 1;
    while (d != a) {
        d *= a;
        d %= mod;
        ++period;
    }
    ull power = pow_mod(b, c, period);
    // power must be positive
    if (power == 0) power = period;

    // show
    print(pow_mod(a, power, mod));
}