[数论](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

伪码:

求a的k次方模p
    当 k 不为 0 时 循环
        若存在 [ k & 1 == 1] 则 [ res = res * a % p] 
        k右移一位
        a平方一次

源码:

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的结果)

思路:

源码:

#include<iostream>
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=a*a%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;
}

本文链接：