CSP-J 2025 第一轮 第 21 题：程序（一）：调用 gcd(36,42) 的返回值

题目

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

调用 $\gcd(36, 42)$ 会返回（ ）。

选项

• A. $6$
• B. $252$
• C. $3$
• D. $2$

答案

A

题解

答案是 A．\(6\)。

gcd(a, b) 用辗转相除法求最大公约数：当 b != 0 时，递归调用 gcd(b, a % b)，其中 % 表示取余；当 b == 0 时，返回 a。

调用过程如下：

``text gcd(36, 42) → gcd(42, 36) // 36 % 42 = 36 → gcd(36, 6) // 42 % 36 = 6 → gcd(6, 0) // 36 % 6 = 0 → 返回 6 ``

这道题只问一次函数调用的返回值，不需要分析 main 中的三重循环。