快速幂

876. 快速幂求逆元 - AcWing题库

AC代码：
 

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;typedef long long ll;int n;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()
{scanf("%d",&n);while(n--){int a,k,p;scanf("%d%d%d",&a,&k,&p);int t=qmi(a,k,p);printf("%d\n",t);}return 0;
}

相关解释：

这里如果暴力做的话，每次都会遍历k次，也就是2*10^9，一共有100000次，显然会超时，所以就需要采用快速幂来求解。

假设要求a得k次方模p的结果，只需要求出a的0次方，a的1次方，...，a的logk次方这些就可以了，将复杂度o（k）转化为o（log k）。每次对于k的最后一位看看是不是1，是1就乘上a（这里a是没k的右移而变化）。这里刚开始是第0位，所以乘上a，如果是第1位，就需要乘上a^2，第2位就需要乘上a^4，所以每次都a乘以a更新a就可以了。

还有一点，一般数论的题要开long long，并且两个数相乘的话，要在前面加个（ll）。