题意简述
给定 (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_2cdots p_c)，故我们可以将 (n | x^m - x) 这个式子拆成由 (c) 个形如 (x^m equiv x ({ m mod} p_i)) 的同余方程组成的同余方程组。
我们先对第 (i) 个方程求出 ([1, p_i]) 内满足条件的数的数量，记为 (s_i)。显然这些解 ({ m mod} p_i) 均不相同，故 (s_i) 即 (x) 在 ({ m 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{ m mod }p])。
存在一种做法是使用线性筛在接近线性的时间内求所有 ([1, p_i]) 内的数的 (m) 次幂，然后暴力判断。不过这里，介绍一种更简单的方法。
首先给出以下结论：给定 (m) 和 (p)，且 (p) 为质数，那么有：
证明如下：
我们要求满足 (x in [1, p]) 时 (x^m equiv x ({ m mod} p)) 的 (x) 的个数。
首先 (x = p) 一定满足，故不特殊考虑，最后答案 (+1) 即可。接下来只考虑 (x in [1, p - 1]) 的情况。由于 (p) 为质数，因此 (p) 存在一个原根 (g)，([1, p - 1]) 内的任意数在 ({ m mod} p) 意义下都可以表示为 (g^y) 的形式。这样，原方程就转化为：
[g^{my} equiv g^y ({ m mod} p) ]根据费马小定理：
[my equiv y ({ m mod} p - 1) Rightarrow (m - 1)y equiv 0 ({ m mod} p - 1) ]令 (k = gcd(m - 1, p - 1))，两边同时除以 (k)，得：
[frac{m - 1}{k}y equiv 0 ({ m 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 hicksim k - 1) 倍）均满足条件，因此 (y) 共有 (k) 种合法取值。
因此满足 (sum_{x = 1}^p[x ^ m equiv x{ m mod }p]) 的 (i) 共有 (k + 1) 个。
这样，本题的时间复杂度就从 (O(sum p_i)) 优化至了 (O(c imes 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
", 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
", ans);
}
return 0;
}