為了真正理解這題，所以我決定好好寫個解題報告。
我是看了後來發的解題報告寫的，按他所說，我們分兩種情況考慮。
第一種：當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
