P1618题解

一、朴素枚举

题目要求将数字 1~9 各使用一次,组成三个三位数 ,使它们的比例为 。

最直接的想法,是在 100~999 的范围内枚举三个数,再检查比例和数字组成:

1
2
3
4
5
for (int x = 100; x <= 999; ++x)
for (int y = 100; y <= 999; ++y)
for (int z = 100; z <= 999; ++z) {
// 检查比例与各数位
}

这样有大约 组候选,时间复杂度为 。但三个数并不是独立的:题目已经给出了它们之间的比例关系。

若第一个数确定,是否能直接生成另外两个数?为了理解整数比例的结构,先讨论两个数。

二、两个整数之比的定理

定理 1:设 均为正整数,满足

如果 是最简整数比,即

那么存在正整数 ,使得

特别地,、。

证明:由比例相等,交叉相乘得到

因为 ,根据贝祖等式,存在整数 ,满足

这里 不必为正数。两边乘以 :

将 代入,得到

也就是

由于 是整数,所以 。于是存在正整数 ,使 。代回 ,得

约去正整数 ,便有 。因此

证毕。

三、推广到 n 个整数

最简整数比并不意味着各个数两两互质。例如 6:10:15 中,任何两个数都有大于 1 的公约数,但

因此,这三个数的比例已经是最简整数比。

定理 2:设两组正整数满足

且

则必然存在一个正整数 ,使得对所有 都有

证明:由比例关系,存在正有理数 ,使得

推广的贝祖等式说明:当整组数的最大公约数为 1 时,存在整数 ,满足

两边乘以 ,再代入 ,得到

右边是整数的线性组合,因此 必为整数。又因为 ,令 ,就得到

证毕。

这个结论只要求整组数的最大公约数为 1,并不要求两两互质。

四、回到题目:实际上不必计算 gcd

设要求的三个三位数为 ,满足

如果 的最大公约数不为 1,可以先除以

化成最简整数比,再应用定理 2。但在具体实现中,完全不需要真的去求这个 。

因为只要 ,原比例本身就已经给出

无论 是否互质,这两条等式都成立。于是只需枚举第一个数

再由比例生成 。

但要注意:生成的 不一定是整数。C++ 的整数除法会舍去小数部分,因此不能仅凭计算结果认定比例成立。

我的处理方式是:先计算整数候选值,再反过来检查

只有这两个等式同时成立,生成的整数才真正符合比例。最后再检查三个数是否都是三位数,以及九个数位是否恰好为 1~9。

当 时,题目中的第一个数不可能同时为正的三位数,直接输出 No!!! 即可。

五、C++ 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;

bool check(int x, int y, int z) {
bool used[10] = {};
for (int num : {x, y, z}) {
for (int i = 0; i < 3; ++i) {
int d = num % 10;
if (d == 0 || used[d]) return false;
used[d] = true;
num /= 10;
}
}
return true;
}

int main() {
int A, B, C;
cin >> A >> B >> C;

if (A == 0) {
cout << "No!!!\n";
return 0;
}

bool found = false;
for (int x = 123; x <= 987; ++x) {
int y = x * B / A;
int z = x * C / A;

// 整数除法可能截断:反向检查等比例关系
if (y * A != x * B || z * A != x * C) continue;
if (y < 100 || y > 999 || z < 100 || z > 999) continue;

if (check(x, y, z)) {
cout << x << ' ' << y << ' ' << z << '\n';
found = true;
}
}
if (!found) cout << "No!!!\n";
}

因为第一个数 从小到大枚举,输出自然已按第一个数升序排列。

六、复杂度分析

三重枚举的时间复杂度是 。现在只枚举第一个三位数,共最多 900 次;每次生成另外两个数、反向验证比例及检查九个数位,都只需常数时间。因此,时间复杂度降为

空间复杂度为 。

七、总结

特别要注意,枚举法并不依赖 互质。只要使用交叉相乘验证,就能正确处理最大公约数大于 1 的输入。