CSP-J 2025 第一轮 第 17 题：程序（一）：删去 gcd(i,k)==1 是否影响结果

题目

#include <algorithm>
#include <cstdio>
#include <cstring>
inline int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
int main() {
    int n;
    scanf("%d", &n);
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            for (int k = j + 1; k <= n; ++k) {
                if (gcd(i, j) == 1 && gcd(j, k) == 1
                    && gcd(i, k) == 1) {
                    ++ans;
                }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

将第 $16$ 行中的 && gcd(i,k)==1 删去不会影响程序运行结果。（ ）

选项

• √. 正确
• ×. 错误

答案

×

题解

答案：×，错误。

删去这个条件后，程序只检查 i 与 j 互质、j 与 k 互质，但这不能保证 i 与 k 互质。

例如，当 \(n \ge 4\) 时，取 \(i=2,\ j=3,\ k=4\)：

• \(\gcd(2,3)=1\)，满足；
• \(\gcd(3,4)=1\)，满足；
• \(\gcd(2,4)=2\)，不满足。

原程序不会统计这个三元组，删除条件后却会统计，因此结果会改变。

关键：互质关系不具有传递性。