此题用到的公式：a^b%c=a^(b%phi(c)+phi(c))%c (b>=phi(c)).
1.当n!<phi(p)时，直接暴力掉；
2.当n!>=phi(p) && n!%phi(p)!=0,用上面公式求；
3.当n!>=phi(p) && n!%phi(p)==0,变为n^(phi(p))%p,找循环节，就可以了
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstdlib>
#include<vector>
#define ll unsigned __int64
using namespace std;
ll an[];
ll euler(ll n)
{
ll ans=;
for(int i=;i*i<=n;i++)
{
if(n%i==)
{
ans*=i-;
n/=i;
while(n%i==)
{
ans*=i;
n/=i;
}
}
}
if(n>) ans*=n-;
return ans;
}
ll pows(ll a,ll b, ll mod)
{
ll ans=;
while(b)
{
if(b&) ans=(ans*a)%mod;
b>>=;
a=(a*a)%mod;
}
return ans%mod;
}
int main()
{
int t,k=;
ll m,ans,fac,c,i,j,phi,b,p;
cin>>t;
while(t--)
{
scanf("%I64u%I64u%I64u",&b,&p,&m);
printf("Case #%d: ",++k);
if(p==)
{
if(m==18446744073709551615U)
printf("18446744073709551616\n");
else printf("%I64u\n",m+);
continue;
}
ans=;fac=;
phi=euler(p);
//n!<phi(p)
for(i=;i<=m&&fac<=phi;i++)
{
if(pows(i,fac,p)==b)
ans++;
fac*=(i+);
}
fac%=phi;
//n!>=phi(p) && n!%phi(p)!=0
for(;i<=m&&fac;i++)
{
if(pows(i,fac+phi,p)==b)
ans++;
fac=(fac*(i+))%phi;
}
//n!>=phi(p) && n!%phi(p)==0
if(i<=m)
{
ll cnt=;
// memset(an,0,sizeof(an));
for(j=;j<p;j++)
{
an[j]=pows(i+j,phi,p);
if(an[j]==b)
cnt++;
}
c=(m-i+)/p;
ans+=c*cnt;
ll remind=(m-i+)%p;
for(j=;j<remind;j++)
if(an[j]==b)
ans++;
}
printf("%I64u\n",ans);
}
return ;
}