这就是大神口中的简单题，我的数论简直烂到不行，这些数学出身的家伙何必出这些恶心的数学题来难为我们呢。。
用到一个公式 A^x%P=(A^(x%phi(P)+phi[P]))%P (x>=phi[C])，phi[C]表示欧拉函数。
注意条件是x>=phi[C]，但这题的x是增长很快的，很快就能满足这个条件，所以x<phi[C]这部分暴力即可。
接着继续暴力求x%phi[C]!=0的情况，很快就会出现x%phi[C]==0，并且之后一直都会满足，题目转化为求A^phi[P]%P==b，根据鸽巢原理，一定会出现长度为P循环节，于是统计循环节内满足条件的数的个数，再乘以循环节个数，然后在暴力统计一下多余长度内有多少个数满足条件即可。
一个很大的trick就是结果会超LongLong，达到2^64，这里需要特判。。
1 #include <string.h> 2 #include <stdio.h> 3 #define MAXN 100005 4 typedef unsigned long long ULL; 5 int cas; 6 ULL m,ans,n,fac,tot,b,p; 7 ULL phi[MAXN],mod[MAXN]; 8 //A^x%P=A^(x%phi(P)+phi[P])%P (x>=phi[C]) 9 void init(){ 10 for(int i=1;i<MAXN;i++)phi[i]=i; 11 for(int i=2;i<MAXN;i+=2)phi[i]/=2; 12 for(int i=3;i<MAXN;i+=2)if(phi[i]==i){ 13 for(int j=i;j<MAXN;j+=i)phi[j]=phi[j]/i*(i-1); 14 } 15 } 16 ULL pow(ULL a,ULL x){ 17 ULL ret=1; 18 for(ULL tmp=a;x;x>>=1){ 19 if(x&1){ 20 ret*=tmp; 21 if(ret>=p)ret%=p; 22 } 23 tmp*=tmp; 24 if(tmp>=p)tmp%=p; 25 } 26 return ret; 27 } 28 int main(){ 29 //freopen("test.in","r",stdin); 30 init(); 31 scanf("%d",&cas); 32 for(int ca=1;ca<=cas;ca++){ 33 scanf("%I64u%I64u%I64u\n",&b,&p,&m); 34 //TRICK! p==1&&c==0&&m=2^64-1 溢出 35 if(m==18446744073709551615ULL&&p==1ULL&&b==0ULL){ 36 printf("Case #%d: 18446744073709551616\n",ca); 37 continue; 38 } 39 ans=n=tot=0,fac=1; 40 //step1;n!<=phi[p] 41 for(;n<=m&&fac<phi[p];n++,fac*=n) 42 if(pow(n,fac)==b)ans++; 43 //step2:n!%phi[p]!=0 44 fac%=phi[p]; 45 for(;n<=m&&fac;n++,fac=fac*n%phi[p]) 46 if(pow(n,fac+phi[p])==b)ans++; 47 //step3:n!%phi[p]==0 48 if(n<=m){ 49 ULL rel=m-n+1; 50 for(ULL i=0;i<p;i++){ 51 mod[i]=pow(n+i,phi[p]); 52 tot+=(mod[i]==b?1:0); 53 } 54 ans+=(ULL)tot*(rel/p); 55 rel%=p; 56 for(ULL i=0;i<rel;i++){ 57 ans+=(mod[i]==b?1:0); 58 } 59 } 60 printf("Case #%d: %I64u\n",ca,ans); 61 } 62 }