CSP-J 2025 第一轮 第 20 题：程序（一）：输入为 8 时的输出

题目

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

当输入为 $8$ 的时候，输出为（ ）。

选项

• A. $37$
• B. $42$
• C. $35$
• D. $25$

答案

D

题解

程序统计的是：从 $1$ 到 $8$ 中选出三个不同的数，使它们两两互质，共有多少种选法。

三重循环保证 $i<j<k$，所以每组选出的三个数只会统计一次。条件中的三个 gcd 都等于 $1$，要求的是两两互质，不能只看三个数的共同最大公约数是否为 $1$。

可以按选出的偶数个数分类计数。两个偶数的最大公约数至少为 $2$，所以符合条件的三个数中至多有一个偶数。

1. 不选偶数。 奇数为 $1,3,5,7$，它们两两互质。从中任选三个都符合条件，共有

$$\binom{4}{3}=4$$ 种。

1. 恰好选一个偶数。
2. 偶数为 $2、4、8$ 时，它与四个奇数 $1,3,5,7$ 都互质。因此每个偶数都可以搭配任意两个奇数，共有

$$3\times\binom{4}{2}=18$$ 种。

• 偶数为 $6$ 时，不能搭配 $3$，因为 $\gcd(6,3)=3$。只能从 $1,5,7$ 中选两个，共有

$$\binom{3}{2}=3$$ 种。

因此，最终的计数为 $$ans=4+18+3=25.$$

程序输出 25，选择 D。