本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-06 19:08:23

题解里头似乎没有离线的做法。实际上，用离线来做，不仅更快，而且更好写。

题意即求

$$ \begin{cases} x-\dfrac yz = n!\ \dfrac {x-y} z = (n-1)! \ x\ge 0, z \ge 1 \end{cases} $$

的 $(x, y, z)$ 数量。

前两式相减，消去 $\dfrac y z$，得到

$$ \dfrac {x(z-1)}z = (n-1)!(n-1) $$

当 $z = 1$ 时，代入原式发现 $n! = (n-1)!$，即 $n = 1$，于是 $n = 1$ 时有无数解。

当 $z \gt 1$ 时，

$$ x = (n-1)!(n-1) \dfrac z{z-1} $$

于是 $z - 1$ 是 $(n-1)!(n-1)$ 的因子。由于这个条件是充要的，所以原方程的解数就是右式的因子数。

显然这玩意儿没法直接算。但我们知道，一个数的因子数，就是它唯一分解后质因子指数的任意组合，也即 $\prod (\lpha_i+1)$。

于是现在的问题，就转化为怎么快速做出 $T$ 个 $n$ 的 $(n - 1)!(n-1)$ 的每个质因子的指数。

对于单个 $n$，我们可以枚举 $i$ 从 $2$ 到 $n - 1$，动态维护一个答案 $p$，表示从 $1$ 到 $i - 1$ 的 $\prod (\lpha_i + 1)$。显然的，我们分解出 $i$ 后，它对于 $p$ 的贡献是 $\dfrac {\lpha'_i+\lpha_i+1}{\lpha'_i+1}$（其中 $\lpha'_i$ 表示前 $i - 1$ 个数分解出来的这一位上的指数）。由于是模意义，除法改用逆元。

但本题单单是根号分解就已经过不去了。

可以考虑线性筛筛出每个数的最小质因子，然后从最小质因子开始做分解；于是，复杂度从根号降到对数。

这样，我们就知道了怎么在 $O(n\log n)$ 时间内算出一个 $n$ 的答案。

下面考虑对于 $T$ 个 $n$，怎么快速进行计算。

非常显然地，对于 $n \le m$，那么对 $n$ 进行的计算，是被包含在对 $m$ 进行的计算中的。也就是说，如果我们暴力按刚才的方法，以 $O(Tn\log n)$ 时间来算，实际上会进行许多无用功。

于是我们可以考虑离线，然后排序，这样就可以消除无用的计算。维护一个 $u$ 表示下一个要分解的数，于是就可以 $n + T\log n$ 计算出所有询问的答案。

代码实现很简单。

#include <iostream>
#include <algorithm>
#include <bitset>
#define fi first
#define se second
#define int long long
using namespace std;
using pi = pair<int, int>;
const int N = 1e6 + 10, P = 998244353;
int mn[N], primes[N], res[N], s[N], inv[N], nr = 0;
pi z[N];

\/\/ 线性筛求最小质因子
void sieve (int n)
{
	for (int i = 2; i <= n; i++) {
		if (!mn[i]) ++nr, mn[primes[nr] = i] = nr;
		for (int j = 1; primes[j] * i <= n; j++) {
			mn[i * primes[j]] = j;
			if (i % primes[j] == 0) break;
		}
	}
}

signed main (void)
{
	int m;
	
	cin.tie (0)->sync_with_stdio (false);
	\/\/ 离线并开筛
	cin >> m;
	for (int i = 1; i <= m; i++) cin >> z[i].fi, --z[i].fi, z[i].se = i;
	sort (z + 1, z + m + 1), sieve (z[m].fi);
	
	\/\/ 线性预处理逆元
	inv[1] = 1;
	for (int i = 2; i <= z[m].fi; i++) inv[i] = (P - P \/ i) * inv[P % i] % P;
	
	int i = 1, ans = 1;
	
	\/\/ 特判无解情况
	while (!z[i].fi && i <= m) res[z[i++].se] = -1;
	for (int u = 2; i <= m; i++) {
		\/\/ 筛掉 (n - 1)! 中的质因子，并动态维护 ans
		for (; u <= z[i].fi; u++) {
			int v = u;
			while (v > 1) {
				int w = mn[v], cnt = 0;
				while (v % primes[w] == 0) v \/= primes[w], cnt++;
				ans = ans * inv[s[w] + 1] % P * (s[w] + cnt + 1) % P, s[w] += cnt;
			}
		}
		
		\/\/ 筛 (n - 1) 项，更新到当前询问的 ans 上
		int prod = ans, val = z[i].fi;
		while (val > 1) {
			int w = mn[val], cnt = 0;
			while (val % primes[w] == 0) val \/= primes[w], cnt++;
			prod = prod * inv[s[w] + 1] % P * (s[w] + cnt + 1) % P;
		}
		res[z[i].se] = prod;
	}
	
	for (int i = 1; i <= m; i++)
		if (res[i] == -1) cout << "inf\n";
		else cout << res[i] << '\n';
	return 0;
}