[语言月赛202302] 最澄澈的空与海 题解

· · 题解

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)。这也是题目中构造方案的来源。