自动搬运

查看原文

来自洛谷，原作者为

	Maxmilite **

搬运于2025-08-24 21:14:33，当前版本为作者最后更新于2023-02-09 12:31:21，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Source & Knowledge

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

文字题解

题目大意

给定一个整数 $n$，帮助求出一组整数 $x, y, z$，满足 $x - y \div z = n!$ 且 $(x - y) \div z = n$。

解析

本题考察分析问题的能力和对单重循环的运用。

正如题目所言，直接输出 $2 \times (n! - n)$、$2 \times (n! - 2n)$、$2$ 即可通过本题。关于这组答案的合理性题目也已经给出，难点在于计算 $n!$ 的部分。下面给出 $n! = 1 \times 2 \times \cdots \times n$ 的计算方法。

建立一个初值为 $1$ 的变量 $ans$ 用于存储 $n!$ 的结果。之后循环 $1 \sim n$ 枚举变量，对 $1 \sim n$ 中的每个整数 $i$，将 $ans$ 赋值为 $ans \times i$。这个过程使用 for 循环实现。

for 循环的格式为：

for (起始条件; 循环能够继续的条件; 循环完成后进行变量更新的语句) {
	// ...
}

具体的控制流可以参考 https://www.runoob.com/cplusplus/cpp-for-loop.html，由于篇幅限制这里不再做过多的描述。

最后的 $ans$ 即为 $n!$ 的结果，正确性是显然的。由于计算过程中做的均为乘法运算，因此可以将 $ans$ 的初始值设置为 $1$。

核心代码：

int ans = 1;
for (int i = 1; i <= n; ++i) {
	ans *= i;
}

特别的，当 $n = 0$ 时，循环部分不会进行，此时 $ans = 1$，也是符合要求的。

最后输出 $2 \times (ans - n)$、$2 \times (ans - 2n)$、$2$ 即可。

视频题解

完整代码请在视频中查看。

补充内容

以下内容可能会用到一些初高中数学知识，完成本题不需要以下内容，可以选择性阅读。

实际上初始题目并没有给出构造方案，后来受到了难度限制，因此给出了一组构造方案。

下面来解析一下如何得出本题的构造方案。

首先给出两条引理，用于对后面的构造方案进行解释。

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

证明：

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

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

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

证毕。

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

证明：

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

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

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

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

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

证毕。

因此，我们只需要找到 $(n! - n)$ 的一个因数，将其 $+ 1$ 后作为 $z$，计算出 $x = (n! - n) \times \dfrac{z}{z - 1}$，$y = z \times (x - n!)$ 即可。由上面的引理，这样的解总是存在的。

显然 $1$ 一定是 $(n! - n)$ 的因数。所以可以令 $z =1 + 1 = 2$，这时 $x = (n! - n) \times 2$，$y = 2 \times (n! - 2n)$。这也是题目中构造方案的来源。