快速幂

思路:利用[ 反复平方法 ] 将 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; }

本文链接：