快速幂（a^b mod p）的模板（递归和迭代）

快速幂的递归写法

typedef long long ll;
ll binaryPow(ll a,ll b,ll m){
    if(m==1) return 0;
    if(b==0) return 1;
    a%=m;
    if(b&1) return a*binaryPow(a,b-1,m)%m;
    else {
        ll mul=binaryPow(a,b/2,m);
        return mul*mul%m;
    }
}

快速幂的迭代写法

typedef long long ll;
ll binaryPow(ll a,ll b,ll m){
    if(m==1) return 0;
    ll ans=1%m;
    while(b>0){
        if(b&1) ans=ans*a%m;
        a=a*a%m;
        b>>=1;
    }
    return ans;
}

ps:

1. b&1等价于b%2==1
2. b>>=1等价于b=b/2

细节注意：

1. 如果初始是a有可能大于等于m，那么需要先让a对m取模。
2. 如果m为1，可以直接特判为0（因为任何正整数对1取模一定等于0）。