hdu4335 What is N?------多校联合4

为了真正理解这题，所以我决定好好写个解题报告。
我是看了后来发的解题报告写的，按他所说，我们分两种情况考虑。
第一种：当n比较大的时候，就是达到n!%phi(p)=0的时候，其实就是求n^phi(p)%p,显而易见的。
              那么比n 小的那部分就直接暴力。
第二种：当n比较小的时候，我们也是暴力了。
这两种其实也就合二为一了，因为都需要暴力的。
[cpp] 
#include<iostream> 
#include<cstdlib> 
#include<stdio.h> 
using namespace std; 
typedef unsigned __int64 ll; 
ll getphi(ll n)//求欧拉函数值 
{ 
    ll ans=1,i; 
    for(i=2;i*i<=n;i++) 
    { 
        if(n%i==0) 
        { 
            n/=i; 
            ans*=i-1; 
            while(n%i==0) 
            { 
                n/=i;ans*=i; 
            } 
        } 
    } 
    if(n>1) ans*=n-1; 
    return ans; 
} 
int powmod(ll a,int b,int c)//a^b%c 
{ 
    int ans=1; 
    while(b) 
    { 
        if(b&1) ans=ans*a%c; 
        b>>=1; 
        a=a*a%c; 
    } 
    return ans; 
} 
int main() 
{ 
    int t,b,p; 
    int count=1; 
    ll m; 
    scanf("%d",&t); 
    while(t--) 
    { 
        cin>>b>>p>>m; 
        int phi=getphi(p);//phi(p); 
        ll mul=1;int num;ll ans=0;int add=0; 
        for(int i=0;i<=p;i++) 
        { 
            mul*=i?i:1; 
            if(mul>=phi) add=phi; 
            mul%=phi; 
            if(!mul){num=i;break;}//找到n!%p==0的临界值了 
            if(i<=m)// 
            if(powmod(i,mul+add,p)==b) ans++; 
        } 
 
        for(int i=0;i<p&&i<=m;i++) 
        { 
            if(powmod(i,phi,p)==b) 
            { 
                ans+=(m-i)/p+1;//这里想一下就知道了 
                if(num>=i+1)//这个地方还真容易忽视。。。 
                ans-=(num-1-i)/p+1; 
            } 
        } 
 
         if(m== 18446744073709551615LL&&p == 1&&b == 0) 
        { 
            printf("Case #%d: 18446744073709551616/n", count++); 
        } 
        else 
        printf("Case #%d: %I64u/n", count++, ans); 
    } 
    return 0; 
} 

作者：qiqijianglu