数学知识——快速幂的理解及例题

快速幂：快速的求出来a^k mod p的结果。

1<=a,k,p<=1e9。

快速幂其实就是预处理出来：

 于是a^k可以表示为（二进制表示）：

 说明一下：出来a^(2^0)=a以外，其余的预处理一直都在平方。

 例题：875. 快速幂 - AcWing题库

题面：

 

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
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()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    while(n--)
    {
        int a,k,p;
        cin>>a>>k>>p;
        cout<<qmi(a,k,p)<<endl;
    }
    return 0;
}