lcm(12, 18) 是多少
运行下面这段程序:
本节模型:my_gcd(a, b) 辗转相除求最大公约数,my_lcm(a, b) = a / gcd * b 求最小公倍数。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
long long my_gcd(long long a, long long b) {
// 辗转相除:gcd(a, b) = gcd(b, a % b),直到 b 为 0
while (b != 0) {
long long r = a % b;
a = b; b = r;
}
return a;
}
long long my_lcm(long long a, long long b) {
// 最小公倍数 = a * b / gcd,先除后乘防溢出
return a / my_gcd(a, b) * b;
}
int main() {
cout << my_lcm(12, 18) << endl;
}
(本题用 g++ -std=c++17 -O0 编译。)
全部评论