C++高速べき乗型取り+大数乗算型取り

ll qmul(ll x, ll y, ll mod)   //       ，   p * p  LL       ； O(1)            (   )
{
    ll ret = 0;
    while(y) {
        if(y & 1)
            ret = (ret + x) % mod;
        x = x * 2 % mod;
        y >>= 1;
    }
    return ret;
}
ll qpow(ll a, ll n, ll mod)
{
    ll ret = 1;
    while(n)
    {
        if(n & 1) ret = qmul(ret, a, mod);
        a = qmul(a, a, mod);
        n >>= 1;
    }
    return ret;
}

いくつかの数が連続して最後に型を取る場合、各数字を先に型を取り、最後に型を取ることができ、すなわち、%は*に対して結合則を有する.しかし,型取りに用いる数自体が大きいと,上記の方法ではだめである.このとき,高速べき乗型取りの方法を参考にして,大数相乗型取りの効果を達成することができる.