Upd on 2023.10.14 08:21：修改了推式子和题意的一些小错误。
前言
一道恐怖的绿题。显然我认为应该是蓝题。（不过在这篇题解写到一半的时候升蓝了，感谢 @StudyingFather。）
名字挺好的。
题意
给定 \(n\)，求出满足以下条件的三元组 \((x, y, z)\) 的组数：
-
\(x \ge 0, z \ge 1\)。
-
\(x - \frac{y}{z} = n!\) 且 \(\frac{x - y}{z} = \frac{n!}{n}\)。
-
\(z \mid x,z \mid y\)。
答案为 \(\infty\) 时，输出 inf。
多组数据。
解法
首先我们需要将式子变形。最开始，将两式相减，得到：
\[\begin{aligned} x - \frac{y}{z} - \frac{x - y}{z} = n! - \frac{n!}{n} \end{aligned}\]然后继续化简：
\[\begin{aligned} x - \frac{y + (x - y)}{z} &= n! - (n - 1)! \\ x - \frac{x}{z} &= n \times (n - 1)! - (n - 1)!\\ \frac{x \times (z - 1)}{z} &= (n - 1) \times (n - 1)!\\ x &= \frac{(n - 1) \times (n - 1)! \times z}{z - 1} \end{aligned}\]可以发现 \(y\) 被消掉了，于是不再需要考虑 \(y\)。
考虑 \(z > 1\) 的情况，\(x\) 要为整数，那么 \((n - 1) \times (n - 1)! \times z \mid z - 1\)，而在 \(z \ne 2\) 时，显然 \(z \nmid z - 1\)，那么就需要 \((n - 1) \times (n - 1)! \mid z - 1\)。那么这样的 \(x\) 的个数显然就是 \((n - 1) \times (n - 1)!\) 的约数个数。
于是这道题就转化为了求 \((n - 1) \times (n - 1)!\) 的约数个数。
根据约数个数定理和唯一分解定理，设 \(x = p_1^{q_1} \times p_2^{q_2} \times \dots p_k^{q_k}\)，其中 \(p_i\) 为质数，那么 \(x\) 的约数个数为 \(\prod\limits_{i = 1}^{k}{(q_i + 1)}\)。
设 \(dp_i\) 表示 \(i\) 这个质数在 \((n - 1) \times (n - 1)!\) 出现的次数，那么每次的答案即为 \(\prod\limits_{i = 1}^{cnt}{(dp_i + 1)}\)。
不过显然这样质因数分解很慢，考虑优化。
首先考虑线性筛的本质。在线性筛的过程中，每个合数都只会被它最小的质因数标记。考虑把它存下来，这样质因数分解的复杂度就降到了 \(\Theta(\log{n})\)。由于是阶乘，显然需要从 \(1\) 到 \(n - 1\) 枚举，每次都质因数分解存入 \(dp_i\) 中，不然 \(10^6!\)，可想而知。这样的总时间复杂度为 \(\Theta(n \log{n})\) 的，但是如果再加上多测，复杂度就变为了 \(\Theta(T n \log{n})\)，显然是不行的。
考虑继续优化上面的过程。
由于增加了多测，那么我们可以换一种方式，不一定要在线求答案，考虑预处理。
设 \(Ans_i\) 表示 \(i \times i!\) 的答案。将每一个 \(i\) 进行质因数分解，设 \(p\) 为当前分解到的质因数，\(num\) 为这个质因数出现的次数。那么 \(dp_p + num \times 2 \to dp_p\)。这里 \(dp_p\) 乘 \(2\) 的原因是还有一个 \(i\) 要乘。不过根据 \(dp\) 的定义，乘 \(i\) 的答案不能算进来，所以之后将答案存进 \(Ans_i\) 后，还要减去一个 \(num\)。然后将 \(\prod\limits_{i = 1}^{cnt}{(dp_i + 1)}\) 存入 \(Ans_i\)。这时我们会发现处理出 \(\prod\limits_{i = 1}^{cnt}{(dp_i + 1)}\) 是一个很慢的过程。考虑优化这个过程。
设 \(ans\) 为当前 \(\prod\limits_{i = 1}^{cnt}{(dp_i + 1)}\) 的值。对于每一个 \(i\)，将 \(i\) 进行质因数分解。设 \(p\) 为当前分解到的质因数，\(num\) 为这个质因数出现的次数。那么此时的 \(dp_p\) 比上一个 \(dp_p\) 增加了 \(num\)，将 \(ans \div dp_p\)，再将 \(dp_p + num \times 2\)，最后将 \(ans \times dp_p\) 即可。根据前文所说，\(dp_p\) 还需要减去一个 \(num\)，那么在 \(ans\) 存入 \(Ans_i\) 后，将 \(ans \div dp_p\)，\(dp_p - num\)，再将 \(ans \times dp_p\) 即可。
由于 \(ans\) 需要取模，所以这里的除法全部改为乘逆元即可。
最后处理一个特殊情况，前文我们都只考虑了 \(z > 1\) 的情况，当 \(z = 1\) 时，情况就会变成这样：
\[\begin{cases} x - y = n! \\ x - y = \frac{n!}{n} \end{cases}\]那么 \(n! = \frac{n!}{n}\)，显然 \(n = 1\)。
那么这时候，\(x - y = 1\)，符合条件的三元组显然有 \(\infty\) 个，输出 inf 即可。
毒瘤。
AC Code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5, Mod = 998244353;
int t, n, Ans[N], dp[N], pri[N], fac[N], inv[N];
vector<int> prime;
vector< pair<int, int> > f;
bool vis[N];
void Prime(int x)
{
vis[1] = true;
for(int i = 2; i <= x; i++)
{
if(!vis[i])
prime.push_back(i), pri[i] = i;
for(auto p : prime)
{
if(i * p > x)
break;
vis[i * p] = true;
pri[i * p] = p;
if(!(i % p))
break;
}
}
return;
}
void p_fac(int x)
{
f.clear();
while(x != 1)
{
int y = pri[x], cnt = 0;
while(!(x % y))
x /= y, cnt++;
f.push_back(make_pair(y, cnt));
}
return;
}
void Inv(int x)
{
inv[1] = 1;
for(int i = 2; i <= x; i++)
inv[i] = (Mod - Mod / i) * inv[Mod % i] % Mod;
return;
}
void init(int n)
{
Prime(1e6);
Inv(1e6);
int ans = Ans[0] = 1;
for(int i = 1; i <= n; i++)
{
p_fac(i);
for(auto j : f)
{
int p = j.first, num = j.second;
ans = ans * inv[dp[p] + 1] % Mod;
dp[p] += num * 2;
ans = ans * (dp[p] + 1) % Mod;
}
Ans[i] = ans;
for(auto j : f)
{
int p = j.first, num = j.second;
// cout << ans << " " << inv[dp[p] + 1] << " " << dp[p] + 1 << " ";
ans = ans * inv[dp[p] + 1] % Mod;
dp[p] -= num;
ans = ans * (dp[p] + 1) % Mod;
}
}
return;
}
signed main()
{
init(1e6);
cin >> t;
while(t--)
{
cin >> n;
cout << (n == 1 ? "inf" : to_string(Ans[n - 1])) << "\n";
}
return 0;
}