http://blog.csdn.net/ACM_cxlove?viewmode=contents


大意找出多少个N满足下式
范围如此之大啊。结果做法是暴力，囧。 要用到一个降幂公式：http://blog.csdn.net/acm_cxlove/article/details/7829367

A^x = A^(x % Phi(C) + Phi(C)) (mod C) （x>=Phi(C)）

注意括号里的条件，那么当n比较小的时候，就不能用这个了，n比较小，肯定是暴力嘛。
那么第一个阶段便是当n比较小，n!小于phi(p)，直接暴力求解。
当n!大于phi（P）的时候，便 可以用上面的降幂公式。还得继续暴力，发现n!%phi(p)会出现0，这是必然的，至少n>=phi(p)为0 ， 那么(n+1)!%phi(p)也为0，这便出现了重复，转变为n^(phi(p))%p==b的问题了。固定了指数，根据鸽巢原理，余数是循环的，那么只
要找出p个的结果，之后通过循环节求解便可以了。
当P为1的时候，b为0，这时候答案是m+1,不过m可能为2^64-1，如果加1的话就溢出了，这里太坑了

#include
#include
#include
#include
#include
#include
#define LL unsigned long long
//#define MOD 1000000007
#define eps 1e-6
#define zero(a)  fabs(a) using namespace std;
LL get_eular(LL m){
LL ret=1;
for(LL i=2;i*i<=m;i++)
if(m%i==0){
ret*=i-1;
m/=i;
while(m%i==0){
m/=i;
ret*=i;
}
}
if(m>1)
ret*=m-1;
return ret;
}
LL PowMod(LL a,LL b,LL MOD){
LL ret=1;
while(b){
if(b&1)
ret=(ret*a)%MOD;
a=(a*a)%MOD;
b>>=1;
}
return ret;
}
LL b,p,m,ring[100005];
int main(){
int t,cas=0;
scanf("%d",&t);
while(t--){
scanf("%I64u%I64u%I64u",&b,&p,&m);
printf("Case #%d: ",++cas);
if(p==1){
//大坑一个，要注意溢出
if(m==18446744073709551615ULL)
                printf("18446744073709551616 ");       
else        
printf("%I64u ",m+1);
continue;
}
LL i=0,phi=get_eular(p),fac=1,ans=0;
//第一个环节，n!for(i=0;i<=m&&fac<=phi;i++){
if(PowMod(i,fac,p)==b)
ans++;
fac*=i+1;
}
fac=fac%phi;
//第二个环节,n^(n!%phi(p)+phi(p))，直到指数固定为phi(p)
for(;i<=m&&fac;i++){
if(PowMod(i,fac+phi,p)==b)
ans++;
fac=(fac*(i+1))%phi;
}
if(i<=m){
LL cnt=0;
//打表一个循环
for(int j=0;jring[j]=PowMod(i+j,phi,p);
if(ring[j]==b)
cnt++;
}
LL idx=(m-i+1)/p;
ans+=cnt*idx;
LL remain=(m-i+1)%p;
for(int j=0;jif(ring[j]==b)
ans++;
}
printf("%I64u ",ans);
}
return 0;
}