2025 年第 19 题阅读程序初等数论普及/提高
程序(一):把 gcd(b,a%b) 改成 gcd(a,a%b) 可能出现的问题
题目
阅读下面的程序,回答问题。 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); } 将 gcd 函数中的 return gcd(b, a % b); 改为 return gcd(a, a % b); 后,程序可能出现的问题是( )
考点拆解
辗转相除法 gcd(a,b)=gcd(b,a%b) 的正确写法
递归参数改写后对结果的影响分析
易错提醒
修改递归调用的参数前,先想清楚原本是靠哪个参数在变小来保证递归收敛和结果正确
阅读程序题要按变量变化顺序手推,不要跳步
选择题要检查单位、边界和题目中的否定词