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

假设函数 gcd() 函数能正确求两个正整数的最大公约数，则下面的 lcm() 函数能求相应两数的最小公倍数。

int lcm(int a, int b) {
    return a * b / gcd(a, 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 五级数学知识模块，考察最小公倍数与最大公约数的关系。命题人卡住的是死记硬背公式却不懂推导的学生，这类题在五级里是数学逻辑推理的基石。