快速幂取余运算

朴素

现在要取a^b/c的余数,而a,c都很大。如果直接pow然后取余肯定会爆。

所以出现了一个定理:ab%c=a%cb%c

for(int i=0;i<b;i++){
a*a%c;
}

快速幂

现在如果b还很大,过了10^8,就很容易爆时间,然后就出现了快速幂:
把b转换成二进制数。

例如:
2^11 mod 5

11的二进制是1011

11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1

ans=(2^(2º%5)%5x2^(2¹%5)%5x2^((2³%5)%5)%5

#include <iostream>
using namespace std;
//注意在这里p时主要的,而不是b。
int main(){
    long long b,p,k;
    
    cin>>b>>p>>k;
    cout<<b<<"^"<<p<<" mod "<<k<<"=";
    long long s=1;
    while(p>0){
        if(p%2==1){//如果p是偶数,即p的二进制最后一位为1时,就要运算了。
            s=s*b%k;
        }
            b=b*b%k;//累乘,用来知道在每一位要乘以多少。
            p=p>>1;//把p的二进制右移一位,即去掉其二进制位的最低位。
    }
    
    cout<<s%k;
    return 0;
} 

本文链接:https://kaispace.com.cn/index.php/archives/301/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者