利用降幂公式。。呃,还是自己去搜题解吧。知道降幂公式后,就不难了。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #define LL unsigned long long using namespace std; bool mod[100005]; LL PHI(LL P){ LL ret=1; for(LL i=2;i*i<=P;i++) if(P%i==0){ ret*=i-1; P/=i; while(P%i==0){ P/=i; ret*=i; } } if(P>1) ret*=P-1; return ret; } LL quick(LL a,LL k,LL m){ LL ret=1; LL t=a%m; while(k){ if(k&1) ret=(ret*t)%m; k>>=1; t=(t*t)%m; } return ret; } int main(){ int T; LL b,P,M; scanf("%d",&T); for(int kase=1;kase<=T;kase++){ scanf("%I64u%I64u%I64u",&b,&P,&M); printf("Case #%d: ",kase); if(P==1){ if(M==18446744073709551615ULL) printf("18446744073709551616 "); else printf("%I64u ",M+1); continue; } LL phi=PHI(P); LL i,ans; LL fac=1; ans=0; for(i=0;i<=M&&fac<=phi;i++){ if(quick(i,fac,P)==b){ ans++; } fac*=(i+1); } fac%=phi; for(;i<=M&&fac;i++){ if(quick(i,fac,P)==b) ans++; fac=(fac*(i+1))%phi; } if(i<=M){ memset(mod,false,sizeof(mod)); LL cn=0; for(LL k=0;k<P;k++){ if(quick(i+k,phi,P)==b){ mod[k]=true; cn++; } } ans+=((M-i+1)/P)*cn; LL e=(M-i+1)%P; for(LL k=0;k<e;k++) if(mod[k]) ans++; } printf("%I64u ",ans); } return 0; }