递归快速幂

//递归快速幂
int qpow(int a, int n)
{
    if (n == 0)
        return 1;
    else if (n % 2 == 1)
        return qpow(a, n - 1) * a;
    else
    {
        int temp = qpow(a, n / 2);
        return temp * temp;
    }
}

非递归快速幂

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

//递归快速幂（对大素数取模）
define MOD 1000000007
typedef long long ll;
ll qpow(ll a, ll n)
{
if (n == 0)
    return 1;
else if (n % 2 == 1)
    return qpow(a, n - 1) * a % MOD;
else
{
    ll temp = qpow(a, n / 2) % MOD;
    return temp * temp % MOD;
}
}