自动搬运

查看原文

来自洛谷，原作者为

	Maxmilite **

搬运于2025-08-24 22:44:31，当前版本为作者最后更新于2023-02-04 00:35:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Source & Knowledge

2023 年 2 月语言月赛，由洛谷网校入门计划/基础计划提供。

文字题解

题目大意

多测，$T$ 组数据。每次给定一个正整数 $n$，求满足 $x \geq 0$，$z \geq 1$，$x - y \div z = n!$ 且 $(x - y) \div z = \dfrac{n!}{n}$ 的整数三元组 $(x, y, z)$ 的数量。$1 \leq T \leq 10 ^ 5$，$1 \leq n \leq 10 ^ 6$。

解析

本题做法可能有很多种，这里提供一种做法。

---

以下先给出两个引理，方便解释后面的做法。

引理 1：对于一个满足条件的整数三元组 $(x, y, z)$，通过 $z$ 可以确定唯一的 $x, y$ 与之对应。

证明：

因为整数三元组 $(x, y, z)$ 满足上述条件，所以 $(x - \dfrac yz) - (\dfrac{x - y}{z}) = n! - \dfrac{n!}n$，即 $x \times \dfrac{z - 1}{z} = (n - 1)! \times (n - 1)$。

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

显然，接下来 $y = x - z \times (n - 1)!$。

证毕。

引理 2：在 $z \geq 2$ 的情况下，一个整数三元组 $(x, y, z)$ 满足上述条件的充要条件为 $z - 1$ 是 $(n - 1)! \times (n - 1)$ 的因数。

证明：

由引理 1，当 $z \geq 2$ 时，$x = (n - 1)! \times (n - 1) \times \dfrac{z}{z - 1}$，$y = x - z \times (n - 1)!$。此时由于 $(n - 1)! > 0$，$n - 1 \geq 0$，$z - 1 \geq 1$，那么我们就可以保证 $x \geq 0$。如果此时 $x, y$ 都是整数，那么这个整数三元组就符合题面要求的所有约束。

考虑如何保证 $x, y$ 都是整数。不难发现如果 $x$ 是整数，$y$ 则一定是整数。因此考虑 $x$ 的问题。

注意到导致 $x$ 不是整数的唯一因素是分母 $z - 1$。因此如果想让 $x$ 是整数，只要保证 $(n - 1)! \times (n - 1) \times {z}$ 可以整除 $z - 1$ 即可。

又 $\gcd(z, z - 1) = 1$（易证，如果 $k$ 是 $z$ 和 $z - 1$ 的因数，那么 $k$ 就是 $z - z + 1 = 1$ 的因数，所以 $k$ 只能是 $1$），所以如果 $(n - 1)! \times (n - 1) \times {z}$ 可以整除 $z - 1$，则只可能为 $z - 1$ 是 $(n - 1)! \times (n - 1)$ 的因数。

对充分性，如果 $z - 1$ 是 $(n - 1)! \times (n - 1)$ 的因数，那么 $x = (n - 1)! \times (n - 1) \times \dfrac{z}{z - 1}$ 就是非负整数，$y$ 同样也是整数。且由引理 1，如果三元组合法，那么当 $z$ 确定时，对应的 $x, y$ 是唯一的。因此一个整数三元组 $(x, y, z)$ 可以满足上述条件。

证毕。

由上面的引理，我们可以发现，对于每个 $(n - 1)! \times (n - 1)$ 的因数 $p$，我们都可以令 $z = p + 1$ 构造出唯一的整数三元组 $(x, y, z)$ 满足题目给出的条件。同时，由引理 $2$，可以得出如果 $z - 1$ 不是 $(n - 1)! \times (n - 1)$ 的因数，则一定不能够构造出满足条件的整数三元组。

因此，满足条件的整数三元组的数量，就是 $(n - 1)! \times (n - 1)$ 的因数数量。考虑如何求 $(n - 1)! \times (n - 1)$ 的因数数量。

根据唯一分解定理和约数个数定理，我们可以将问题转化为求解 $(n - 1)! \times (n - 1)$ 的质因数及每个质因数的数量。

---

首先考虑单组数据的做法。定义一个整数数组 $f$。其中 $f _ i$ 代表「从 $2$ 开始数的第 $i$ 个质数」作为质因数在 $(n - 1)! \times (n - 1)$ 中出现的次数。将 $i$ 从 $1$ 枚举至 $n - 1$，对于每一个 $i$，将其进行质因数分解。设分解后的结果为 $i = p _ 1 ^ {e _ 1} p _ 2 ^ {e _ 2} \cdots p _ k ^ {e _ k}$，对每个 $p _ j$，让 $f$ 中对应的位置增加 $e _ j$。最后将 $n - 1$ 单独多进行一次这个过程。

上述过程完成后，设 $\leq n$ 的质数为 $cnt$ 个，我们计算出 $(1 + f _ 1) \times (1 + f _ 2) \times \cdots \times (1 + f _ {cnt})$ 取模即可作为答案。

对于上述的整套流程，时间上的瓶颈在质因数分解部分。考虑优化质因数分解过程。

考虑线性筛质数的原理。线性筛质数过程中，每个合数都只被标记一次。在这唯一一次标记的过程中，这个合数是被其最小的质因数标记的。在标记的同时，我们考虑记录下这个最小的质因数。

我们使用 $p$ 数组记录线性筛质数过程，$p _ i$ 代表 $i$ 的最小的质因数。这样做的好处是，在进行质因数分解的过程中，我们可以直接找到对应整数的最小质因数直接进行分拆，而不需要从头遍历质数表逐一匹配。不难发现，我们可以在 $\mathcal{O} (\log n)$ 的时间复杂度内完成对 $n$ 的质因数分解。

我们首先进行一次线性筛质数，同时记录下 $p$ 数组。线性筛完成后，进行「将 $i$ 从 $1$ 枚举至 $n - 1$，对于每一个 $i$，将其进行质因数分解」的过程。这样对于单次询问，最终的总时间复杂度为 $\mathcal{O} (n \log n)$。

然而多测的总时间复杂度为 $\mathcal{O} (Tn \log n)$，按照上述方法只能拿到 $60\%$ 的分数。考虑如何优化的多测的过程。

不难发现我们对 $(n - 1)!$ 的质因数及个数进行了多次重复的运算，这是非常耗时的！考虑如何优化这个过程。

如果只是询问 $(n - 1)!$ 的因数数量，我们显然可以进行递推。使用 $h$ 数组记录答案，将 $i$ 从 $1$ 枚举至 $n - 1$，对于每一个 $i$，将其进行质因数分解，每次分解并操作完 $f$ 数组后，计算 $(1 + f _ 1) \times (1 + f _ 2) \times \cdots \times (1 + f _ {cnt})$ 并取模存入 $h _ i$ 中即可。瓶颈转化为了计算 $(1 + f _ 1) \times (1 + f _ 2) \times \cdots \times (1 + f _ {cnt})$。

考虑使用一个变量 $ans$ 记录当前的 $(1 + f _ 1) \times (1 + f _ 2) \times \cdots \times (1 + f _ {cnt})$。在对 $i$ 筛质因数的过程中，我们每筛出一个质因数及对应的数量（设这个质因数为第 $x$ 个质数，出现 $y$ 次），就将 $ans$ 先除以 $1 + f _ {x}$，再乘 $1 + f _ {x} + y$，再让 $f _ x$ 增加 $y$。最后将 $ans$ 存入 $h _ i$ 即可。

由于 $ans$ 需要取模，因此上述的除法转换为乘逆元即可。这样，如果使用线性预处理逆元，我们即可在 $\mathcal{O} (\log n)$ 的时间内完成对 $n$ 的质因数分解和答案 $ans$ 的更新。最终便可 $\mathcal{O} (n \log n)$ 预处理，$\mathcal{O}(1)$ 回答。实际上不使用线性求逆元也可以在时限一半以内通过本题。

但是本题在 $(n - 1)!$ 外还有一个 $(n - 1)$，考虑处理这个 $(n - 1)$。我们在上面的过程中提到了增添一个 $(n - 1)$ 对答案的处理（将 $ans$ 先除后乘，修改 $f$ 数组，将 $ans$ 存入 $h$ 答案数组），这里，我们考虑对单独的 $(n - 1)$ 先增添后撤销。具体的，设 $n - 1$ 的某个质因数为第 $x$ 个质数，出现 $y$ 次，先「对所有的质因数，将 $ans$ 先除以 $1 + f _ {x}$，再乘 $1 + f _ {x} + y$，再让 $f _ x$ 增加 $y$。最后将 $ans$ 存入 $h _ i$」，答案记录完成后再「对所有的质因数，将 $ans$ 先除以 $1 + f _ x$，再乘 $1 + f _ {x} - y$，让 $f _ x$ 减少 $y$。不将 $ans$ 存入 $h _ i$」即可。

这样我们即可在 $\mathcal{O}(n \log n)$ 的时间内完成所有的预处理工作，之后 $\mathcal{O} (1)$ 回答即可。总时间复杂度 $\mathcal{O}(n \log n + T)$。

---

最后有一个特殊情况需要处理。对于引理 2，我们只证明了 $z \geq 2$ 的情况。为什么没有证明 $z = 1$ 呢？显然是因为此时分母是 $z - 1= 0$。

那如果我非要让 $z = 1$ 呢？令 $z = 1$，我们会得到这样的一组式子：

$$\begin{cases} x - y = n! \\ x - y = (n - 1)! \end{cases} $$

会得到 $n! = (n - 1)!$，这个式子成立当且仅当 $n = 1$。此时 $n! = (n - 1)! = 1$。

所以，当 $n = 1$ 时，我们让 $z = 1$，只需让 $x - y = 1$，三元组 $(x, y, z)$ 就是符合要求的。显然这样的三元组有无数个。

所以当且仅当 $n = 1$，输出一行 inf。

代码

标答代码写的很丑陋（诸如没有采用线性求逆元），洛谷上开启 O2 后单个点在 700ms 左右通过，所以考虑后时限设置为两秒。

#include <bits/stdc++.h>
using namespace std;

#define lint long long
#define rep(_, __, ___) for (int _ = __; _ <= ___; ++_)

const int maxn = 1e6 + 5;
const int modint = 998244353;
using pii = pair<int, int>;

namespace FactorSieve {

	int prime[maxn];
	int ans[maxn];
	int p[maxn];
	int cnt;
	int f[maxn];

	lint fpow(lint x, lint y) {
		lint ans = 1;
		while (y) {
			if (y & 1) {
				ans = (ans * x) % modint;
			}
			x = (x * x) % modint;
			y >>= 1;
		}
		return ans;
	}

	lint finv(lint x) {
		return fpow(x, modint - 2);
	}

	pii v[maxn];
	int vcnt = 0;

	void init() {
		for (int i = 2; i <= 1000000; i++) {
			if (!p[i]) {
				p[i] = i, prime[++cnt] = i;
			}
			for (int j = 1; j <= cnt && i * prime[j] <= 1000000; j++) {
				p[i * prime[j]] = prime[j];
				if (p[i] == prime[j])
					break;
			}
		}

		lint cur = ans[0] = 1;

		for (int i = 1; i <= 1000000; ++i) {
			vcnt = 0;
			lint var = i;
			while (var != 1) {
				int cnt = 0, cur = p[var];
				while (var % cur == 0)
					var /= cur, ++cnt;
				v[++vcnt] = make_pair(cur, cnt);
			}
			for (int k = 1; k <= vcnt; ++k) {
				pii j = v[k];
				cur *= finv(1 + f[j.first]);
				cur %= modint;
				f[j.first] += j.second * 2;
				cur *= 1 + f[j.first];
				cur %= modint;
			}
			ans[i] = cur;
			for (int k = 1; k <= vcnt; ++k) {
				pii j = v[k];
				cur *= finv(1 + f[j.first]);
				cur %= modint;
				f[j.first] -= j.second;
				cur *= 1 + f[j.first];
				cur %= modint;
			}
		}
	}

	int query(int x) {
		return ans[x];
	}
};

int main() {
	FactorSieve::init();
	int t;
	scanf("%d", &t);
	while (t--) {
		int n;
		scanf("%d", &n);
		if (n == 1)
			printf("inf\n");
		else
			printf("%d\n", FactorSieve::query(n - 1));
	}
	return 0;
}