クイックべき乗(テンプレート)

任意の整数のモジュールべき乗演算a^b%c bに対してbはバイナリの形式b=b 0+b 1*2+b 2*2^2+...+bn*2^nここで私たちのb 0はbバイナリの第1位に対応しているので、私たちのa^b演算はa^b 0*a^b 1*2*...*a^(bn*2^n)bにとってバイナリビットは0ではなく1である.では、bxが0の場合、私たちの計算結果は1であることを考慮する必要はありません.私たちが本当に望んでいるのはbの非0バイナリビットです.
では、bの0のバイナリビットを除いた式がa^(bx*2^x)*…*a(bn*2^n)であると仮定します.ここで最初に述べた式を適用すると、a^b%c演算は(a^(bx*2^x)%c)…(a^(bn*2^n)%c)に変換できます.我々は高速べき乗の本質に近い(a^(bx*2^x)%c)…(a^(bn*2^n)%c)A 1=(a^(bx*2^x)%c)...An=(a^(bn*2^n)%c)というように、Anは常にA(n-1)の平方倍(もちろん型取り均一速那を加えた)で、順次プッシュされる

ll mod_pow(ll x, ll n, ll mod)
{
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res*x%mod;
        x = x*x%mod;
        n >>= 1;
    }
    return res;
}