冪乗の剰余

概要

繰り返し二乗法で $x^y \ \mathrm{mod} \ m$ を求める． $m$ が素数で $x$ が $m$ の倍数でなければ $x^{m-1} = 1$ である(フェルマーの小定理)．これを利用すると，$x,y$ が非常に大きな数でも計算できる．

計算量

$O(\log m)$

実装

ll modpow(ll x, ll y, ll m) {
    if (y == 0) return 1;
    ll res = modpow(x, y / 2, m);
    return res * res % m * (y & 1 ? x : 1) % m;
}
ll modpow(ll x, ll y) {
    if (y == 0) return 1;
    ll res = modpow(x, y / 2);
    return res * res % MOD * (y & 1 ? x : 1) % MOD;
}
// ll modpow(const string &x, const string &y, ll m) {
//     assert(!(x == "0" && y == "0"));
//     ll N = modstr(x, m);
//     return N == 0 ? (y == "0" ? 1 : 0) : modpow(N, modstr(y, m - 1), m);
// }