- P62's solution
P62's Solution
- 2025-9-14 20:10:15 @
首先 ,然后特判 的情况。
直接建立一张有向图, 表明 能唯一确定 ,由于所有点的出度为 ,这张图一定是若干个 $a \to b \to \ldots \to m \to n \to \ldots \to z \to m \to \ldots$ 的 形(实际上是若干个环),庶出 形的个数 ,答案即为 ,因为 个 形起点处的 值唯一确定了整个序列,并且 。
实际上,进一步的分析表明,求出 对 的阶 ,答案即为 。
#include <bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7;
int power(int b, int k)
{
if (k == 0) return 1;
if (k == 1) return b;
long long s = power(b, k >> 1);
s = s * s % P;
if (k & 1) s = s * b % P;
return s;
}
int main()
{
int n, m;
cin >> n >> m;
if (m <= 1)
{
cout << power(n, n - 1 + m) << endl;
return 0;
}
long long k = m, l = 1;
while (k != 1) k = k * m % n, l++;
cout << power(n, (n - 1) / l) << endl;
return 0;
}