Solution
求$a^k$,我们可以把k变成二进制的形式:
比如若k=3,k=00011B $=2^0+2^1$
若k=5,k=00101B $=2^0+2^2$
我们只需要把每个二进制位对应的a的幂算出来
比如若k=3,k=00011B $=2^0+2^1$
$$a^3=a^{2^0} \times a^{2^1}$$
而我们只需要算$a^{2^0}$和$a^{2^1}$即可
并且我们会发现$a^{2^1}=a^{2^0} \times a^{2^0}$
可以得到如下递推式
$$a^{2^i}=a^{2^{(i-1)}} \times a^{2^{(i-1)}}$$
复杂一些的例子:求3的102次方
102=0110 0110B
$3^{2^0}=3$
$3^{2^1}=3^{2^0} \times 3^{2^0}$
$3^{2^2}=3^{2^1} \times 3^{2^1}$
…
$3^{2^6}=3^{2^5} \times 3^{2^5}$
$$3^{102}=3^{2^6} \times 3^{2^5} \times 3^{2^2} \times 3^{2^1}$$
更新
#include<iostream>
using namespace std;
#include<algorithm>
const int N=1e5+10;
int n,A[N],B[N],C[N];
typedef long long LL;
int quickpow(int a,int b,int c){
LL p=a,res=1;
for(LL i=0,inspect=1;inspect<=b;i++,inspect<<=1){//当b为1e11级别的时候 (int)inspect移到最高位后还会向左移,内存泄漏导致无限循环
if(b>>i&1) res=res*p%c;
p=p*p%c;
}
return res;
}
int main(void){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n;
for(int i=0;i<n;i++) cin>>A[i]>>B[i]>>C[i];
for(int i=0;i<n;i++){
cout<<quickpow(A[i],B[i],C[i])<<endl;
}
}
代码
#include<iostream>
using namespace std;
#include<algorithm>
typedef long intt;
const intt N=100010;
intt a[N],b[N],p[N];
intt result[30];//log以2为底2亿的对数等于 27.575424759098897。
intt pre_pow(intt A,intt B,intt P){
intt i=0,product=1;
result[i++]=A;
for(intt inspect=2;inspect<=B;i++,inspect=inspect<<1){
result[i]=result[i-1]*result[i-1]%P;
}
i=0;
int temp;
while(temp=(B>>i)){
if((temp&1)==1){
product=(result[i]*product)%P;
}
i++;
}
return product;
}
int main(void){
intt n;
cin>>n;
for(intt i=0;i<n;i++){
cin>>a[i]>>b[i]>>p[i];
}
for(intt i=0;i<n;i++){
cout<<pre_pow(a[i],b[i],p[i])<<endl;
}
}