题意简述
给定 \(n, m\)，求 \(n|x^m - x\) 在满足 \(x \in [1, n]\) 时合法的 \(x\) 的数量。答案模 \(998244353\)。单个测试点包含多组数据。
其中 \(n\) 由如下方式给出：
- 给定 \(c\) 个不超过 \(t\) 的质数 \(p_i(i \in [1, c])\)，有 \(n = \prod_\limits{i = 1}^c p_i\)。
所有测试数据满足 \(1 \leq c \leq 50,1 \leq t \leq 10^4,1 \leq m \leq 10^9\)，数据组数 \(\leq 10000\)。
题解
首先，由于已经给出了 \(n\) 的唯一分解式 \(n = p_1p_2\cdots p_c\)，故我们可以将 \(n | x^m - x\) 这个式子拆成由 \(c\) 个形如 \(x^m \equiv x\ ({\rm mod}\ p_i)\) 的同余方程组成的同余方程组。
我们先对第 \(i\) 个方程求出 \([1, p_i]\) 内满足条件的数的数量，记为 \(s_i\)。显然这些解 \({\rm mod}\ p_i\) 均不相同，故 \(s_i\) 即 \(x\) 在 \({\rm mod}\ p_i\) 意义下的合法余数的数量。由于所有 \(p_i\) 均为互不相同的质数，即两两互质，因此可以证明，除了 \(1\) 为公共解外，任意两个方程的解（\([1, p_i]\) 范围内）不存在交集。因此，我们在每个方程中任选一个解，构造一个新的一次同余方程组，共能得到 \(\prod s_i\) 个不同的方程组。由于根据中国剩余定理，每个方程组在 \([1, n]\) 范围内仅有唯一解，因此答案就为 \(\prod s_i\)。
所以，对于第 \(i\) 个方程，我们需要求 \(s_i = \sum_\limits{x = 1}^p[x ^ m \equiv x{\ \rm mod\ }p]\)。
存在一种做法是使用线性筛在接近线性的时间内求所有 \([1, p_i]\) 内的数的 \(m\) 次幂，然后暴力判断。不过这里，介绍一种更简单的方法。
首先给出以下结论：给定 \(m\) 和 \(p\)，且 \(p\) 为质数，那么有：
\]
证明如下：
我们要求满足 \(x \in [1, p]\) 时 \(x^m \equiv x\ ({\rm mod}\ p)\) 的 \(x\) 的个数。
首先 \(x = p\) 一定满足，故不特殊考虑，最后答案 \(+1\) 即可。接下来只考虑 \(x \in [1, p - 1]\) 的情况。由于 \(p\) 为质数，因此 \(p\) 存在一个原根 \(g\)，\([1, p - 1]\) 内的任意数在 \({\rm mod}\ p\) 意义下都可以表示为 \(g^y\) 的形式。这样，原方程就转化为：
\[g^{my} \equiv g^y\ ({\rm mod}\ p)
\]根据费马小定理：
\[my \equiv y\ ({\rm mod}\ p - 1) \Rightarrow (m - 1)y \equiv 0\ ({\rm mod}\ p - 1)
\]令 \(k = \gcd(m - 1, p - 1)\)，两边同时除以 \(k\)，得：
\[\frac{m - 1}{k}y \equiv 0\ ({\rm mod}\ \frac{p - 1}{k})
\]由于此时 \(\gcd(\frac{m - 1}{k}, \frac{p - 1}{k}) = 1\)，因此 \(y\) 一定有 \(\frac{p - 1}{k} | y\)。由于 \(y \in [0, p - 2]\)，显然，\(\frac{p - 1}{k}\) 的任意小于 \(k\) 的非负整数倍（\(0 \thicksim k - 1\) 倍）均满足条件，因此 \(y\) 共有 \(k\) 种合法取值。
因此满足 \(\sum_{x = 1}^p[x ^ m \equiv x{\ \rm mod\ }p]\) 的 \(i\) 共有 \(k + 1\) 个。
这样，本题的时间复杂度就从 \(O(\sum p_i)\) 优化至了 \(O(c \times \log p_i)\)（\(\log\) 为 \(\gcd\) 的复杂度）。
代码
线性筛求幂后暴力判断代码如下（常数莫名其妙很大...）：
#include<bits/stdc++.h>
using namespace std;
#define rg register
const int e = 998244353, N = 1e4 + 10;
int mod, c, m;
inline void add(rg int& x, rg int y) {
x += y, x -= x >= mod ? mod : 0;
}
inline void mul(rg int& x, rg int y) {
x = 1ull * x * y % mod;
}
inline int qpow(rg int v, rg int p) {
rg int res = 1;
for (; p; p >>= 1, mul(v, v)) {
if (p & 1) {
mul(res, v);
}
}
return res;
}
inline int solve(rg int n) {
rg int p[N], f[N], pri[N], t;
mod = n, t = 0;
fill(p + 1, p + 1 + n, 1);
rg int res = 2;
for (rg int i = 2; i < n; ++i) {
if (p[i]) {
pri[++t] = i, f[i] = qpow(i, m);
}
res += (i == f[i]);
for (rg int j = 1, d; j <= t && (d = i * pri[j]) <= n; ++j) {
p[d] = 0;
f[d] = 1ull * f[i] * f[pri[j]] % mod;
if (i % pri[j] == 0) {
break;
}
}
}
return res;
}
int main() {
int T; scanf("%*d%d", &T);
for (rg int kase = 1; kase <= T; ++kase) {
scanf("%d%d", &c, &m);
rg int ans = 1;
for (rg int i = 1; i <= c; ++i) {
rg int x; scanf("%d", &x);
rg int v = solve(x);
mod = e, mul(ans, v);
}
printf("%d\n", ans);
}
return 0;
}
用更简单的方法代码如下：
#include<bits/stdc++.h>
using namespace std;
#define rg register
const int mod = 998244353;
inline void mul(int& x, int y) {
x = 1ll * x * y % mod;
}
int main() {
int T; scanf("%*d%d", &T);
for (rg int kase = 1; kase <= T; ++kase) {
int n, m; scanf("%d%d", &n, &m);
int ans = 1;
for (rg int i = 1; i <= n; ++i) {
int x; scanf("%d", &x);
mul(ans, __gcd(m - 1, x - 1) + 1);
}
printf("%d\n", ans);
}
return 0;
}