CSP-J 2025 第一轮 第 19 题：程序（一）：把 gcd(b,a%b) 改成 gcd(a,a%b) 可能出现的问题

题目

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

将第 $7$ 行的 gcd(b, a%b) 改为 gcd(a, a%b) 后，程序可能出现的问题是（ ）。

选项

• A. 输出的答案大于原答案。
• B. 输出的答案小于原答案。
• C. 程序有可能陷入死循环。
• D. 可能发生整型溢出问题。

答案

B

题解

选 B. 输出的答案小于原答案。

修改后的函数是： ``cpp inline int gcd(int a, int b) { if (b == 0) return a; return gcd(a, a % b); } ``

递归过程中，第一个参数 a 始终不变；第二个参数在非零时严格减小，最终变成 0，于是函数返回最初的 a。所以不会陷入死循环，但计算结果不再是最大公约数。

对于循环中的 i < j < k，有： ``cpp gcd(i, j) == i gcd(j, k) == j gcd(i, k) == i ``

要使判断条件成立，必须同时满足 i == 1 和 j == 1，这与 i < j 矛盾。因此，修改后的程序始终输出 0。

例如 n = 3 时，三元组 (1, 2, 3) 两两互质，原程序输出 1，修改后输出 0，所以选 B。