【QED】等式构造

题目

题目链接🔗

题目描述

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

我们认为这个问题太难了，因此我们把解决这个问题的任务交给了你，相信你可以完成这个任务：给出一个整数 $n$，求出一组整数 $x$，$y$，$z$，满足 $x-y÷z=n!$ 且 $(x-y)÷z=n$。

注意，$z$ 应为正数。如果有多种可能的答案，输出任意⼀种即可。

输入输出格式

【输入格式】

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

【输出格式】

输出共一行三个整数 $x$，$y$，$z$，代表满足 $x-y÷z=n!$ 且 $(x-y)÷z=n$ 的一组整数（$z$为正整数）。三者两两之间以一个空格隔开。

数据范围

$0<n\le 11$，$-10^9\le x$，$y\le 10^9$，$1\le z\le 10^9$。

测试样例

input1：

5

output1：

230 220 2

input2：

1

output2：

2 1 1

思路

题目要求满足：
$$x-y÷z=n!$$$$(x-y)÷z=n$$令 $y=k\cdot z$，$k$ 为整数，上面两个式子联立后消去 ，可得:$$n!+h=k\cdot z+n\cdot 2$$$$z=\frac{n!+k}{n+k}$$分子变形加上一个 $n$ 再减去一个 $n$ 得：$$z=\frac{n+k+n!-n}{n+k}=1+\frac{n!-n}{n+k}$$由于 k为整数，此外没有太多其他约束，而考虑到 $z\ge 1$ 旦对于此式我们只需要求出一组特解即可满足题意，我们可以注意到当 $\frac{n!-n}{n+k}=1$ 时等式成立。这一步是构造的关键。当然我们也可以寻求其他特解，如考虑到$\frac{n!-n}{n+k}$的分子可以被$n$整除，我们直接令分母中的$k=0$，此时$z=(n-1)!$也为整数使用 $\frac{n!-n}{n+k}=1$的特解，可得:$$k=n!-2n$$将$k$代入上述方程得：$$x=2n!-2n$$$$y=2n!-4n$$$$z=2$$
(思路来源于《2024年广东工业大学揭阳校区ACM新生程序设计竞赛题解》)

代码

#include <iostream>
using namespace std;// 计算阶乘的函数
long long fact(long long x) {long long res = 1;for (long long i = 1; i <= x; i++)res *= i;return res;
}int main() {long long n;cin >> n;// 计算 x 和 y 的值long long x = 2 * (fact(n) - n);long long y = 2 * (fact(n) - 2 * n);// 输出结果cout << x << ' ' << y << ' ' << 2;return 0;
}

复杂度分析

时间复杂度

计算阶乘的时间复杂度为 $O(n)$

空间复杂度

使用了常数个额外变量，空间复杂度为 $O(1)$