luogu-B3709 [语言月赛202302] 最澄澈的空与海

GESP二级练习，多层循环和分支练习，难度★★☆☆☆。

luogu-B3709 [语言月赛202302] 最澄澈的空与海

题目要求

题目背景

材料 1：

请小心地计算下面的算式：$138 - 108 \div 6 = ?$

你大概难以置信，这个算式的计算结果竟然是 $5!$

材料 2：

对于一个正整数 $x$，$x! = 1 \times 2 \times \cdots \times (x - 1) \times x$。我们称 $x!$ 为 $x$ 的阶乘。

特别的，$0! = 1$。

显然，「$138 - 108 \div 6 = 5$」是错误的，而「$(138 - 108) \div 6 = 5$」是正确的，所以对材料 1 中的内容，部分读者会认为「作者没有搞清加减乘除的运算优先级关系而犯错」。

然而，材料 1 最后一行的叹号并不是标点符号，而是材料 2 提到的「阶乘」。

考虑到这一点，「$138 - 108 \div 6 = 5! = 1 \times 2 \times \cdots \times 5 = 120$」显然就是正确的了。

题目描述

有关「上述等式为何正确」的问题解决了，然而「如何构造出上述那种让人啼笑皆非的正确等式」成为了一个新的问题。

我们认为这个问题太难了，因此我们把解决这个问题的任务交给了你，相信你可以完成这个任务。

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

实际上可以发现，当 $z = 2$ 时，原式变为 $\begin{cases} x - \cfrac y2 = n! \\ \cfrac x2 - \cfrac y2 = n\end{cases}$，这时，只需要让 $x = 2 \times (n! - n)$，并根据任何一个式子计算出 $y$ 的值（为 $2 \times (n! - 2n)$），即可构成一组合法答案。这样的答案是总是存在的。

因此，按照我们给出的这种方式直接输出 $2 \times (n! - n)$、$2 \times (n! - 2n)$、$2$ 即可通过本题，难点便来到了计算出对应的值上。

当然，你也可以使用其他方法计算出符合要求的 $x, y, z$。

输入格式

输入共一行一个整数 $n$。

输出格式

输出共一行三个整数 $x, y, z$，代表满足 $x - y \div z = n!$ 且 $(x - y) \div z = n$ 的一组整数。

三者两两之间以一个空格隔开。

输入 #1

5

输出 #1

230 220 2

输入 #2

1

输出 #2

2 1 1

数据规模与约定

对于 $100\%$ 的数据，保证 $0 \leq n \leq 11$。

我们会使用自定义校验器检验你的答案是否正确，因此如果有多组答案，你可以输出其中任意一组。

你需要保证 $x, y, z$ 均为整数且 $-10 ^ {18} \leq x, y \leq 10 ^ {18}$，$1 \leq z \leq 10 ^ {18}$，否则自定义校验器将直接认定您的答案错误。

请注意式子中的 $\div$ 不是向下取整的整除，这显然意味着你需要保证 $y \div z$ 和 $(x - y) \div z$ 为整数。

容易证明，满足条件的 $x, y, z$ 一定存在。

题目分析

解题思路

1. 首先，我们需要理解题目的核心要求：

   • 找到满足条件的整数解 $x, y, z$

2. 解题思路：

   • 需要找到满足 $x - y \div z = n!$ 且 $(x - y) \div z = n$ 的整数解
   • 通过计算 $n$ 的阶乘来得到 $n!$
   • 使用循环尝试不同的 $z$ 值，直到找到满足条件的 $x, y, z$

3. 具体实现：

   • 读入整数 $n$
   • 计算 $n$ 的阶乘
   • 使用循环从 $z = 1$ 开始尝试
   • 对于每个 $z$，计算分子 $z \times (n! - n)$
   • 检查分子是否能被 $z - 1$ 整除
   • 如果能整除，计算 $x$ 和 $y$ 的值
   • 输出满足条件的 $x, y, z$ 并结束程序

{% include custom/custom-post-content-inner.html %}

示例代码

#include <iostream>
using namespace std;
int main() {
    int n; // 定义变量n
    cin >> n; // 输入n的值
    long long factorial = 1; // 初始化阶乘为1
    if (n != 0) {
        for (int i = 1; i <= n; i++) {
            factorial *= i; // 计算n的阶乘
        }
    }
    for (long long z = 1; ; z++) { // 从1开始无限循环
        if (z == 1) {
            if (n == 1) {
                cout << 1 << " " << 0 << " " << 1 << endl; // 输出特殊情况的结果
                break; // 跳出循环
            } else {
                continue; // 继续下一轮循环
            }
        } else {
            long long numerator = z * (factorial - n); // 计算分子
            if (numerator % (z - 1) == 0) {
                long long x = numerator / (z - 1); // 计算x的值
                long long y = x - z * n; // 计算y的值
                cout << x << " " << y << " " << z << endl; // 输出结果
                break; // 跳出循环
            }
        }
    }
    return 0;
}

{% include custom/custom-post-content-footer.md %}

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP 认证学习微信公众号