GESP 五级 · GESP 202512 C++ 五级 第 17 题

假设函数 gcd() 函数能正确求两个正整数的最大公约数，则下面的 lcm(a, b) 函数能正确找到两个正整数 $ a $ 和 $ b $ 的最小公倍数。

int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

辗转相除法求最大公约数：gcd(a,b) = gcd(b, a%b)，当b=0时返回a。时间复杂度O(log min(a,b))。

辗转相除法中gcd(a,b)和gcd(b,a)结果相同。注意a和b的顺序不影响结果。

【考点】最大公约数｜最小公倍数｜整数除法

1. 🎯 考纲定位

GESP 五级算法模块明确要求掌握 GCD 与 LCM 的关系。命题人把这道题放在这里，就是看你是否理解「最小公倍数可由最大公约数推导」这个核心结论，而不是硬编码公式。