[数论](4)快速幂
快速幂
思路:利用[ 反复平方法 ] 将 a 的 k 次方 分解为 [ a²的0次方、a²的1次方、a²的2次方......a²的k次方 ]
例如求[ 4 的 5次方 模6 ],5的二进制表示为101,则结果等于[ 4的2的0次方 % 6 ] * [ 4的2的2次方 % 6]
答案为 1*4=4
伪码:
```C++ 求a的k次方模p 当 k 不为 0 时 循环 若存在 [ k & 1 == 1] 则 [ res = res * a % p] k右移一位 a平方一次
源码:
```C++
LL q_pow(LL a,LL k,LL p){
LL res=1;
while(k){
if(k&1) res=res*a%p;//判断这位上是否为1
k>>=1;
a=a*a%p;//a的2次方的下一位
}
return res;
}
快速幂的应用(求乘法逆元)
这里利用快速幂求乘法逆元(快速幂的优势:log k的时间复杂度求出a的k次方模p的结果)
思路:
源码:
```C++
include
using namespace std; typedef long long LL; int n; LL q_pow(LL a,LL k,LL p){//快速幂模板 LL res=1; while(k){ if(k&1) res = res a % p; k>>=1; a=aa%p; } return res; } int main(){ //给定n个a和p,求乘法逆元x scanf("%d",&n); while(n--){ LL a,p; scanf("%lld %lld",&a,&p); if(a%p==0) printf("impossible\n");//a和p不互质 else printf("%lld\n",q_pow(a,p-2,p));//根据费马小定理[当p为质数时可用快速幂] } return 0; }