题解 | 求最小公倍数

这其实是一道数学题，两个数a，b的最小公倍数等于a*b/gcd(a,b),gcd表示两者的最大公约数.

所以这道题我们就转为求两个数的最大公约数了。我们可以采用辗转相除法来解决该题：

对两个正整数来说，让较小除以两数的模，chong这其实是一道数学题，两个数a，b的最小公倍数等于a*b/gcd(a,b),gcd表示两者的最大公约数. 所以这道题我们就转为求两个数的最大公约数了。我们可以采用辗转相除法来解决该题： 两个正整数的最大公约数，等于较小的数和它们模的最大公约数。所以我们可以借助这个，让两个数不断地变化，当余数为0时，此时的除数就是两者的最大公约数。1997 ÷ 615 = 3 (余 152)615 ÷ 152 = 4(余7)152 ÷ 7 = 21(余5)7 ÷ 5 = 1 (余2)5 ÷ 2 = 2 (余1)2 ÷ 1 = 2 (余0)至此，最大公约数为1

所以我们便可以借助这个性质来编写代码

有的人可能会有疑惑，不是说较小的数和它们的余数么？可是你写gcd的时候并没有管ab的大小啊？

其实不论谁除谁都是可以的，如果大除小自然是没有问题的；如果是小除大，则会将其转化为大除小。看实例：

• 例1：求 48 和 18 的最大公约数48÷18=2 余 12 → 18÷12=1 余 6 → 12÷6=2 余 0 → GCD=6。
• 例2：调换顺序求 18 和 48 的最大公约数18÷48=0 余 18 → 48÷18=2 余 12 → 后续步骤同例1 → GCD=6。

#include <iostream>
using namespace std;

int gcd(int a, int b)
{
    if(b == 0)
        return a;
    return gcd(b, a%b);
}

int main()
{
    int a = 0, b = 0;
    cin >> a >> b;
    cout << (a*b/gcd(b,a)) << endl;
    return 0;
}