快速幂--模板

快速幂：求a^n

int fastPow(int a,int n)
{
    int base=a;//基数
    int res=1;
    while(n)//当幂不为零时
    {
        if(n&1)//幂的二进制分解
        {
            res=((ll)res*base)%mod;
        }
        base=((ll)base*base)%mod;
        n>>=1;
    }
    return res;
}

 快速幂:求a^k%p

例题：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
#define ll long long
int qmi(int a,int k,int p)
{
    int res=1;
    while(k)
    {
        if(k&1)res=(ll)res*a%p;
        k>>=1;
        a=(ll)a*a%p;
    }
    return res;
}
int main()
{
    int a,b,p;
    cin>>a>>b>>p;
    int ans=qmi(a,b,p);
    printf("%d^%d mod %d=%d",a,b,p,ans);
    return 0;
}