学步园

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4335

题意：给定b,p,m( 0<=b<P, 1<=P<=10^5, 1 <= M <=2^64 – 1 ),求满足n^(n!)=b(mod p)且0<=n<=m的n有多少个。 

理论支撑： 

具体证明见：http://blog.csdn.net/longshuai0821/article/details/7826126

解法： n如果很大,n>=phi(p),那么n! mod phi(P) 为0， 于是问题等价为 n^phi(p)=b(mod p)

于是我们可以求得

ni=ci(mod p)，由于如果ni是方程的一个解，那么ni+k*p也是方程的解，所以只需要暴力phi(p)--phi(p)+p-1里面的解就可以了

求的方法无非就是暴力FOR + 二分求幂 即可

对于比较小的n,我们可以采取暴力枚举的方法

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
typedef unsigned long long LL;
const int N=100500;
int phi[N];
void get_phi()
{
    for(int i=1;i<N;i++) phi[i]=i;
    for(int i=2;i<N;i++)
        if(phi[i]==i)
            for(int j=i;j<N;j+=i)
                phi[j]=phi[j]/i*(i-1);
}
LL exp_mod(LL a,LL b,LL mod)
{
    LL ret=1,base=a%mod;
    while(b)
    {
        if(b&1) ret=ret*base%mod;
        b>>=1;
        base=base*base%mod;
    }
    return ret;
}
int main()
{
    get_phi();
    int t;
    scanf("%d",&t);
    LL b,p,m,ans;
    for(int cas=1;cas<=t;cas++)
    {
        scanf("%I64u%I64u%I64u",&b,&p,&m);
//        if(cas==13)
//            cout<<b<<' '<<p<<' '<<m<<endl;
        ans=0;
        if(b==0) ans=1;
        LL mul=1;
//        cout<<phi[p]<<endl;
        for(LL i=1;i<phi[p]&&i<=m;i++){
            mul*=i;
            if(mul>phi[p]) mul=(mul%phi[p]+phi[p]);
            if(exp_mod(i,mul,p)==b) ans++;
        }
//        cout<<ans<<endl;
        for(LL i=phi[p];i<phi[p]+p&&i<=m;i++){
            if(exp_mod(i,phi[p],p)==b)
            {
                ans+=(m-i)/p+1;
            }
        }
        char s[100];
        sprintf(s,"%I64u",ans);
        if(ans==0&&b==0){//答案==2^64时越界处理
             ans-=1;
             sprintf(s,"%I64u",ans);
             s[strlen(s)-1]++;
        }
        printf("Case #%d: %s\n",cas,s);
    }
    return 0;
}