2015
05-23

# What is N?

(This problem is really old&easy and any acmer who is good at math may solve it in second)
As we know, math is both intangible and specific. Today you are going to solve the following math problem:
Given one non-negative integer b, one positive number P and one positive integer M, how many n could you find to satisfy the following 2 rules?

Here n! means n factorial , 0!=1,1!=1,2!=2,3!=6…,n!=(n-1)!*n

In the first line of the input , we have one integer T indicating the number of test cases. (1 <= T <= 20)
Then T cases follows.
For every case, only 3 integers (b, P and M) in a single line. ( 0<=b<P, 1<=P<=10^5, 1 <= M <=2^64 �C 1 )

In the first line of the input , we have one integer T indicating the number of test cases. (1 <= T <= 20)
Then T cases follows.
For every case, only 3 integers (b, P and M) in a single line. ( 0<=b<P, 1<=P<=10^5, 1 <= M <=2^64 �C 1 )

3
1 2 3
2 3 4
3 4 5

Case #1: 2
Case #2: 0
Case #3: 0

A^x=A^(x%phi(p)+phi(p)(mod p)…其中,x>=phi(m)

#include <iostream>
#include <vector>

#ifdef _WIN32
#define LL unsigned __int64
#define out64 "%I64u"
#define in64 "%I64u"
#else
#define LL unsigned long long
#define out64 "%llu"
#define in64 "%llu"
#endif

#define cl(a) memset(a,0,sizeof(a))
#define ss(a) scanf("%d",&a)
#define sl(a) scanf(in64,&a)
#define pb push_back

using namespace std;

const int N=100100;
int a[N],c[N],e[N],p,b;
LL m;

void prime()
{
int i,j;
for (i=2;i<N;i++)
if (!a[i])
{
for (j=i*2;j<N;j+=i)
{
if (!a[j]) c[j]=i;
a[j]=1;
}
}
}

void euler()
{
int i,k;
for (i=2;i<N;i++)
if (!a[i]) e[i]=i-1;
else
{
k=i/c[i];
if (k%c[i]==0) e[i]=c[i]*e[k];
else e[i]=(c[i]-1)*e[k];
}
}

LL js(int x,int y)
{
LL k=y,r=x,res=1;
while (k>0)
{
if (k&1) res=(res*r)%p;
r=(r*r)%p;
k>>=1;
}
return res;
}

void print(int cas,LL z)
{
printf("Case #%d: "out64"\n",cas,z);
}

int main()
{
int T,i,cas;
ss(T);
prime();
euler();
for (cas=1;cas<=T;cas++)
{
ss(b);ss(p);sl(m);
if (p==1)
{
if (m==18446744073709551615ULL)
printf("Case #%d: 18446744073709551616\n",cas);
else print(cas,m+1);
continue;
}
LL n=0,r=1,z=0;
while (r<e[p]&&n<=m)
{
if (js(n,r)==b) z++;
n++;
r*=n;
}
r=r%e[p];
while (r!=0&&n<=m)
{
if (js(n,e[p]+r)==b) z++;
n++;
r=(r*n)%e[p];
}
if (n>m)
{
print(cas,z);
continue;
}
if (n>0) n--;
else if (b==0) z++;
for (i=0;i<p;i++)
if (js(i,e[p])==b)
{
LL k1=0,k2=0;
if (m>=i) k1=(m-i)/p+1;
if (n>=i) k2=(n-i)/p+1;
z=z+(k1-k2);
}
print(cas,z);
}
return 0;
}