CSP-J 2025 第一轮 第 18 题：程序（一）：n≥3 时是否总输出正整数

题目

#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;
}

当输入的 $n \geq 3$ 的时候，程序总是输出一个正整数。（ ）

选项

• √. 正确
• ×. 错误

答案

√

题解

选 √，正确。

程序统计的是：在 \(1\) 到 \(n\) 中，有多少组 \(i<j<k\)，使这三个数两两互质。

当 \(n\ge 3\) 时，一定能取到 \((i,j,k)=(1,2,3)\)，且 \[ \gcd(1,2)=\gcd(2,3)=\gcd(1,3)=1。 \] 因此，ans 至少会增加一次。它初始为 \(0\)，之后只增不减，所以最终有 \(ans\ge 1\)，输出正整数。

这里按此类题目的通常约定，不考虑整数溢出。