题目描述

快速幂

将指数转化成二进制，利用二次幂以O（logk）的时间复杂度进行模运算

时间复杂度

利用普通循环：O(n);
快速幂：O(logk);

C++ 代码

#include<iostream>
using namespace std;
typedef long long LL;

int qmi(int a,int k,int p)
{
    int res=1;
    while(k)
    {   //若二进制最低位为1,则第一次相当于零次幂仍然等于a
        if(k&1)res=(LL)res*a%p;    //后面的运算中res已经不断变化了，相当于只是又乘了一个a
        k>>=1;           //左移一位,将第二位放到最低位
        a=(LL)a*a%p;        //相当于将底数平方,因为上面将指数的二进制减了一位
    }
    return res;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,k,p;
        cin>>a>>k>>p;
        cout<<qmi(a,k,p)<<endl;
    }
    return 0;
}