HDU 4335 What is N? 多校4（数论）

大意找出多少个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