题解 | #求最小公倍数#

a、b的最大公倍数 = a * b / a、b的最大公约数
最大公约数用更相减损法来求，即让两个数相减，然后用差和减数的较大值和较小值更新被减数和减数，直到被减数和减数相等为止，此时被减数就是最大公约数。

#include <bits/stdc++.h>
using namespace std;

// 利用最大公倍数和最大公约数的关系
// 两个数的最大公倍数 = 两个数相乘 / 最大公约数
// 例：8和10的最大公约数==2，最大公倍数=8*10/2=40
// 求最大公约数的方法是辗转相减法，将两个数相减，然后取减数和差相减

int greatestcommondivisor(int a, int b) {
    // 求a和b的最大公约数Minus and minuend
    int minuend = max(a, b);  // 被减数
    int minus = min(a, b);  // 减数

    int difference = 0;
    while (minus != minuend) {
        difference = minuend - minus;
        minuend = max(minus, difference);
        minus = min(minus, difference);
    }
    return minus;
}

int main() {
    int a, b;
    while (cin >> a >> b) {
        int gcdivisor = greatestcommondivisor(a, b);  // 最大公约数
        cout << a * b / gcdivisor << endl;

    }
    return 0;
}

递归写法

#include <bits/stdc++.h>
using namespace std;

// 利用最大公倍数和最大公约数的关系
// 两个数的最大公倍数 = 两个数相乘 / 最大公约数
// 例：8和10的最大公约数==2，最大公倍数=8*10/2=40
// 求最大公约数的方法是辗转相减法，将两个数相减，然后取减数和差相减


int func(int minuend, int minus) {
    if (minuend == minus) return minuend;
    int difference = minuend - minus;
    return func(max(minus, difference), min(minus, difference));  // 这个递归貌似并没有重复计算
    // 这道题中的原问题和子问题有相同的问题结构，是指都是两者相减，直到两者相等
}

int main() {
    int a, b;
    while (cin >> a >> b) {
        // int gcdivisor = greatestcommondivisor(a, b);  // 最大公约数
        int gcdivisor = func(max(a, b), min(a, b));

        cout << a * b / gcdivisor << endl;

    }
    return 0;
}