HDU 4335 What is N?

Description

　　(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

Input

  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 )

Output

　　For each test case, first you should print "Case #x: " in a line, where x stands for the case number started with 1. Then one integer indicates the number of "n" that you can find.

Sample Input

31 2 3

2 3 4

3 4 5

Sample Output

Case #1: 2Case #2: 0

Case #3: 0

同样是欧拉函数降次，当阶乘大于phi(P)时，之后的指数都是phi(P)，所以按照对p取模的余数分类即可。

#include<set>
#include<map>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define loop(i,j,k) for (int i = j;i != -1; i = k[i])
#define lson x << 1, l, mid
#define rson x << 1 | 1, mid + 1, r
#define ff first
#define ss second
#define mp(i,j) make_pair(i,j)
#define pb push_back
#define pii pair<int,LL>
#define inone(x) scanf("%d", &x);
#define intwo(x,y) scanf("%d%d", &x, &y);
using namespace std;
typedef unsigned long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-4;
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
int T, n, m, cas = 0;
LL M;

int phi(int x)
{
  int res = 1;
  for (int i = 2; i*i <= x; i++)
  {
    if (x%i) continue;
    res *= i - 1;
    for (x /= i; !(x%i); res *= i, x /= i);
  }
  return res * max(x - 1, 1);
}

int get(int x, int y, int z)
{
  int res = 1;
  for (; y; y >>= 1)
  {
    if (y & 1) res = 1LL * res*x%z;
    x = 1LL * x*x%z;
  }
  return res;
}

int main()
{
  inone(T);
  while (T--)
  {
    intwo(n, m);  scanf("%llu", &M);
    if (m == 1)
    {
      if (M == 18446744073709551615) printf("Case #%d: 18446744073709551616\n", ++cas);
      else printf("Case #%d: %llu\n", ++cas, M + 1); continue;
    }
    int mod = phi(m), g = 1, f = 0;
    LL ans = (!n)*(M / m + 1);
    rep(i, 1, min(M, (LL)m - 1))
    {
      if (1LL * g * i >= mod) f = 1;
      g = 1LL * g * i % mod;
      ans += get(i, g + f * mod, m) == n;
      ans += (get(i, mod, m) == n) * (M / m + (M % m >= i) - 1);
    }
    printf("Case #%d: %llu\n", ++cas, ans);
  }
  return 0;
}