1
//非递归快速幂
2
int qpow(int a, int n){
3
    int ans = 1;
4
    while(n){
5
        if(n&1) //如果n的当前末位为1
6
            ans *= a; //ans乘上当前的a
7
        a *= a; //a自乘
8
        n >>= 1; //n往右移一位
9
    }
10
    return ans;
11
}

1
//泛型的非递归快速幂
2
template <typename T>
3
T qpow(T a, ll n)
4
{
5
    T ans = 1; // 赋值为乘法单位元，可能要根据构造函数修改
6
    while (n)
7
    {
8
        if (n & 1)
9
            ans = ans * a; // 这里就最好别用自乘了，不然重载完*还要重载*=，有点麻烦。
10
        n >>= 1;
11
        a = a * a;
12
    }
13
    return ans;
14
}

1
//求 m^k mod p，时间复杂度 O(logk)。
2
int qmi(int m, int k, int p)
3
{
4
    int res = 1 % p, t = m;
5
    while (k)
6
    {
7
        if (k&1) res = res * t % p;
8
        t = t * t % p;
9
        k >>= 1;
10
    }
11
    return res;
12
}