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;
}