华华教月月做数学 题解

题目大意：

给你三个数A,B,P,求

快速幂模板题/xk

但是，我们注意到，P的值很大，可以达到,所以，我们不能直接打快速幂，我们需要搞个龟速乘进去。

代码：

#include<bits/stdc++.h>
using namespace std;
inline unsigned long long ksc(unsigned long long x,unsigned long long y,unsigned long long p){
    unsigned long long ans=0;
    while(y){
        if(y&1){
            ans=(ans+x)%p;
        }
        x=(x+x)%p;
        y>>=1;
    }
    return ans;
}
inline unsigned long long ksm(unsigned long long x,unsigned long long y,unsigned long long p){
    unsigned long long ans=1;
    while(y){
        if(y&1){
            ans=ksc(ans,x,p);
        }
        x=ksc(x,x,p);
        y>>=1;
    }
    return ans;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        unsigned long long A,B,P;
        scanf("%llu%llu%llu",&A,&B,&P);
        printf("%llu\n",ksm(A,B,P));
    }
    return 0;
}

但是，龟速乘实在是烦，我们强烈要求取代龟速乘，怎么办？

我们直接用__int128储存中间计算结果就好辣！

#include<bits/stdc++.h>
using namespace std;
inline unsigned long long ksc(__int128 x,__int128 y,unsigned long long p){
    x*=y;
    return x%p;
}
inline unsigned long long ksm(unsigned long long x,unsigned long long y,unsigned long long p){
    unsigned long long ans=1;
    while(y){
        if(y&1){
            ans=ksc(ans,x,p);
        }
        x=ksc(x,x,p);
        y>>=1;
    }
    return ans;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        unsigned long long A,B,P;
        scanf("%llu%llu%llu",&A,&B,&P);
        printf("%llu\n",ksm(A,B,P));
    }
    return 0;
}

关于龟速乘

它死了/x