Rainy2k
0%

快速幂

Posted on Edited on

快速幂方法1：
311=31×32×383^{11} = 3^1 \times 3^2 \times 3^8

1
2
3
4
5
6
7
8
9
10
long long qpow(long long x,int n,long long mod) {
    long long res = 1;
    while(n>0) {
        if(n&1) // 二进制最低位为1，则乘上x^(2^i)
            res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

快速幂方法2：
若n为奇数，那么 ans=(x2)n2×xans = {(x^2)}^{\frac{n}{2}} \times x

1
2
3
4
5
6
7
8
9
// n&1 : (x^2)^(n/2)*x
long long mod_pow(long long x,int n,long long mod) {
    if(n==0)
        return 1;
    long long res = mod_pow(x * x % mod, n / 2, mod);
    if(n&1)
        res = res * x % mod;
    return res;
}