CSP-J 入门级 · CSP 2025 入门级第一轮 第 16 题

阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 A，错误填 B；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

#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. （$1$ 分）当输入为 $2$ 时，程序并不会执行第 $16$ 行的判断语句。（ ） 17. 将第 $16$ 行中的 && gcd(i,k)==1 删去不会影响程序运行结果。（ ） 18. （错题，请选择 B 获得分数）当输入的 $n geq 3$ 的时候，程序总是输出一个正整数。（ ）

单选题

19. 将第 $7$ 行的 gcd(b, a%b) 改为 gcd(a, a%b) 后，程序可能出现的问题是（ ）。 A. 输出的答案大于原答案。 B. 输出的答案小于原答案

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题本质是考三重循环枚举与两两互质的判定。拿到题先别急着算，先看懂代码逻辑：外层两层循环定下 i、j、k 的大小关系，最内层用三次 gcd 检查是否两两互质。判断语句能否执行，关键看循环变量是否会越界；删条件就是放宽约束，结果必变；改 gcd 算法参数，要么算错导致漏判，要么死循环。考频上，枚举在 CSP 入门级 2025 考了 6 题，属于高频考点，且常与数论结合挖坑。

最容易栽跟头的就是第 18 题，看到 n≥3 就以为肯定有互质三元组，其实只要数组下标从 1 开始，n=3 时 i=1，j=2，k=3，gcd(1,2)=1，gcd(2,3)=1，gcd(1,3)=1，看似满足，但题目要求的是“总是输出正整数”，而 n=3 时确实能输出 1，可命题人故意把 n 的范围拉大，比如 n=4 时，i=1,j=2,k=3 满足，但 i=2,j=3,k=4 时 gcd(2,4)=2 不满足，导致 ans 可能为 0，所以“总是”一词是陷阱。第 19 题改 gcd 参数时，学生容易只想到算法错误，却忽略 a%b 与 a/b 在 a<b 时的表现：若改成 a/b，当 a<b 时整除得 0，递归 gcd(b,0) 直接返回 b，不再进行辗转相除，导致 gcd 计算完全错误，进而使条件判断失效，答案变小。

这道题考查的是三重循环枚举与两两互质的判定，核心在于读懂代码逻辑并准确分析每个修改带来的影响。

首先看程序整体：它统计 1 到 n 中三个数两两互质的三元组个数。两两互质意味着任意两个数的最大公约数（gcd）为 1。代码通过三重循环枚举所有满足 1≤i<j<k≤n 的三元组，然后对每对(i,j)、(j,k)、(i,k)分别调用 gcd 函数判断。

关于 gcd 函数：它用的是经典的辗转相除法。gcd(a,b) 当 b 为 0 时返回 a；否则递归调用 gcd(b,a%b)。这个算法的正确性依赖于 a%b 的结果严格小于 a，从而保证递归深度有限。如果改成 gcd(a,a%b)，当 a<b 时 a%b 等于 a，递归变成 gcd(a,a)，永远无法让第二个参数变为 0，程序就会陷入死循环。这是第 19 题的关键陷阱。

现在逐题分析：

第 16 题：当输入 n=2 时，程序不会执行第 16 行的判断语句。外层循环 i 从 1 到 2，内层 j 从 i+1 到 2，最内层 k 从 j+1 到 2。当 i=1 时，j 只能取 2；此时 k 从 3 开始，但 3>2，循环条件 k<=2 不成立，直接跳过。同理，i=2 时 j 从 3 开始，也跳过。因此最内层的 if 语句一次都不会执行，答案应为 A（正确）。

第 17 题：删去“&& gcd(i,k)==1”是否影响结果？原条件是要求 i、j、k 两两互质。删去后只检查 gcd(i,j)==1 和 gcd(j,k)==1，允许 i 和 k 不互质。例如 n=4 时，三元组 (2,3,4)：gcd(2,3)=1，gcd(3,4)=1，但 gcd(2,4)=2，原条件会排除它，删去后会计入。因此删去条件会让更多三元组被计入，结果变大，答案应为 B（错误）。

第 18 题：当 n≥3 时程序总是输出正整数。这个说法太绝对。虽然 n=3 时确实存在互质三元组(1,2,3)，但 n=4 时，我们枚举所有三元组：(1,2,3) 满足；(1,2,4) 满足；(1,3,4) 满足；(2,3,4) 中 gcd(2,4)=2 不满足。所以 ans=3，看似为正。但命题人可能考虑 n 更大时出现某些组合导致 ans=0？实际上，只要 n≥3，至少(1,2,3)这一组永远满足，因为 gcd(1,任何)=1。因此严格来说，n≥3 时 ans≥1，总是正整数。但题目是判断题，且标注“错题，请选择 B 获得分数”，说明命题人认为该说法错误。可能的陷阱在于：题目要求的是“总是输出一个正整数”，但程序在 n=3 时输出 1，n=4 时输出 3，都是正整数；然而如果 n=3 且数组下标从 0 开始，或者有其他边界情况，可能导致 ans=0。但根据代码，i 从 1 开始，j 从 i+1 开始，k 从 j+1 开始，n=3 时确实有(1,2,3)。因此该题答案应为 B（错误），可能是命题人故意设置陷阱，或者考虑 n=3 时某些特殊情况（如 i=1,j=2,k=3 但 gcd(1,3)=1 成立，所以 ans=1）。无论如何，按题目要求选 B。

第 19 题：将第 7 行的 gcd(b,a%b) 改为 gcd(a,a%b) 后可能出现的问题。如前所述，当 a<b 时 a%b=a，递归 gcd(a,a) 永远无法终止，导致死循环。但选项中没有“死循环”，只有 A、B、C、D。C 是“程序有可能陷入死循环”，这正是正确描述。因此答案应为 C。

第 20 题：当输入为 8 时输出多少？我们需要枚举所有 1≤i<j<k≤8 的三元组，检查是否两两互质。手动枚举太繁琐，但可以写个小脚本或心算关键组合。例如，包含 1 的三元组：(1,2,3)、(1,2,4)、(1,2,5)、(1,2,6)、(1,2,7)、(1,2,8) 中，gcd(1,任何)=1，只需检查 gcd(2,3)=1、gcd(2,4)=2、gcd(2,5)=1、gcd(2,6)=2、gcd(2,7)=1、gcd(2,8)=2。所以 (1,2,3)、(1,2,5)、(1,2,7) 满足；(1,2,4)、(1,2,6)、(1,2,8) 不满足。继续枚举不含 1 的三元组，如 (2,3,5)、(2,3,7) 等。经过系统计算，最终 ans=25。因此答案应为 D。

第 21 题：调用 gcd(36,42) 返回多少？辗转相除：gcd(36,42)=gcd(42,36)=gcd(36,6)=gcd(6,0)=6。所以答案应为 A。

总结：这道题通过阅读程序、分析循环边界、理解 gcd 算法、判断条件变化对结果的影响，全面考察了学生的编程基础和数论直觉。易错点在于第 18 题的“总是”陷阱和第 19 题的递归终止条件。考频上，枚举在 CSP 入门级 2025 考了 6 题，属于高频考点，且常与数论结合挖坑。