大意找出多少個N滿足下式
范圍如此之大啊。結果做法是暴力，囧。
要用到一個降冪公式
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的話就溢出了，這裡太坑了
[cpp]
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<cmath>
#define LL unsigned long long
//#define MOD 1000000007
#define eps 1e-6
#define zero(a) fabs(a)<eps
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\n");
else
printf("%I64u\n",m+1);
continue;
}
LL i=0,phi=get_eular(p),fac=1,ans=0;
//第一個環節，n!<phi(p)
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;j<p;j++){
ring[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;j<remain;j++)
if(ring[j]==b)
ans++;
}
printf("%I64u\n",ans);
} www.2cto.com
return 0;
}
作者：ACM_cxlove
