欧几里得算法

求最大公约数只需要欧几里得算法（辗转相除法）$\gcd(a, b)$

求最小公倍数需要用到最大公约数与最小公倍数的关系：$lcm(a, b) = \frac{a * b}{\gcd(a, b)} = \frac{a}{\gcd(a, b)} * b$

可以看到，程序先做除法后做乘法，这样可防止计算过程中发生溢出

例题： 求最大公约数

代码实现：

#include <iostream>

int main() {
    int a, b;
    std::cin >> a >> b;

    while (b) {
        int c = a % b;
        a = b;
        b = c;
    }

    std::cout << "gcd=" << a << '\n';

    return 0;
}