题目大意：题意：告诉你p和k，其中(0<=k<=p-1)，x属于{0,1,2,3,....,p-1}，f函数要满足f(k*x%p)=k*f(x)%p,f(x)的范围必须在[0.p-1]内，问这样的f函数有多少个。
思路：数学题不会写啊啊啊啊。。 一般这种题和费马小定理有关系，寻找循环节。
我们可以发现当k = 0 是答案为 p ^ (p - 1)
k = 1 时答案为p ^ p
否则
首先我们知道f(0) = 0;
我们到最小的 r 使得 k ^ r % p == 1。
那么f(x) == k ^ r * f(x) == k ^ (r - 1) * f(k * x % p) == k ^ (r - 2) * f(k ^ 2 * x % p) ......... == f(k ^ r * x % p) == f(x % p) == f(x)
所以我们可以知道我们挑选了一个f(x)的值之后，我们就能确定 r 个函数的值。
所以我们只要挑(p - 1) / r 个值就能确定全部函数， 因为 k ^ (p - 1) % p == 1 k ^ r % p == 1
所以r一定能整除(p - 1)。 所以答案就是 p ^ ((p - 1) / r);
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define pii pair<int,int>
#define piii pair<int, pair<int,int> > using namespace std; const int N = 2e5 + ;
const int M = + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-; LL fastPow(LL a, LL b) {
LL ans = ;
while(b) {
if(b & ) ans = ans * a % mod;
a = a * a % mod; b >>= ;
}
return ans;
} LL p, k;
int main() { scanf("%lld%lld", &p, &k);
if(k == ) {
printf("%lld\n", fastPow(p, p - ));
} else if(k == ) {
printf("%lld\n", fastPow(p, p));
} else {
int m = ;
for(LL j = k; j != ; j = j * k % p) {
m++;
}
printf("%lld\n", fastPow(p, (p - ) / m));
}
return ;
}
/*
*/