hdu4335 降幂公式 模循环节

2019-04-14 16:20发布

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;
}