遇到数论题就要推式子!
提供最美丽的latex
分析时间复杂度
\[\sqrt a:分解 \\log2(a)*log2(b):快速幂 \\log2(a):逆元 \\ \sqrt{5e7}*(log2(5e7)+log2(5e7) \\≈7071*(26+26) \\=特别快 \]ACcode
#include<bits/stdc++.h>
using namespace std;
int x,y,a,b,cnt,flag,m=9901;
void ojld(int a,int b){
if(!b){
x=1;
y=0;
return;
}
ojld(b,a%b);
int t=y;
y=x-a/b*t;
x=t;
return;
}
int pw(int a,int b){
int sum=1;
while(b){
if(b&1){
sum=(sum%m*a%m+m)%m;
}
b>>=1;
a=(a%m*a%m+m)%m;
}
return sum%m;
}
signed main(){
cin>>a>>b;
int ans=1;
for(int i=2;a!=1;i++){
int zhi=0;
if(a%i==0){
while(a%i==0){
a/=i;
zhi++;
}
}
else{
continue;
}
int fz,fm;
fz=(pw(i,zhi*b+1)-1+m)%m;
int t=i-1;
ojld(t,m);
fm=(x%m+m)%m;
ans=(ans%m*fz%m*fm%m+m)%m;
}
cout<<ans%m;
return 0;
}
标签:a%,int,题解,sumdiv,return,above,log2,poj1845,5e7
From: https://www.cnblogs.com/lewisak/p/18146979