题解 | #最小公倍数#

最小公倍数

最小公倍数

/*
2022年09月20日 17:47:56
最小公倍数
找出最大的，然后逐次++，判断是否能同时对a、b取模
*/
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b; // 假设a < b
    int ret = max(a, b);
    while(true){
        if(ret % a == 0 && ret % b == 0)
            break;
        else
            ret++;
    }
    cout << ret;
}

/*
2022年09月20日 21:46:07
优化算法：最小公倍数 = 两数相乘/最大公约数 
最大公约数用辗转相除法
9 6
9%6=3
6 3
6%3=0
最大公约数就是3
注意数据太大相乘会溢出
*/
#include <iostream>
#include <algorithm>
using namespace std;

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

int main() {
    long long a, b;
    cin >> a >> b;
    long long t = gcd(a, b);
    cout << a*b/t << endl; // 50000 * 50000 会溢出
}