题目
正整数A和正整数B 的最小公倍数是指 能被A和B整除的最小的正整数值，设计一个算法，求输入A和B的最小公倍数。
输入描述：
输入两个正整数A和B。
输出描述：
输出A和B的最小公倍数。
示例
输入
5 7
输出
35
解析
最小公倍数：2个整数公有的倍数叫这2个数的公倍数，其中最小的公倍数叫最小公倍数。
最小公倍数求法：
最小公倍数 = 两数乘积 ÷ 最大公约数
求最大公约数的算法：
- 辗转相除法
- 相减法
- 穷举法
辗转相除法
辗转相除法，也叫欧几里德算法。
两个整数a、b（a >= b），如果a mod b = 0，那么a和b的最大公约数是b。
原理：
设整数a、b最大公约数为z，a >= b，那么a mod z = 0, b mod z = 0， <=> a = kz，b = tz，其中k，t为整数。
设a对b的余数为c，即c = a mod b <=> a = bj + c ，j是整数
=> a - bj = c
=> kz - tzj = c
=> (k - tj)z = c
=> c也能被z整除
因此，a、b的最大公约数，等价于求a、b余数c（a mod b）和b的最大公约数。而c <= min(a, b)，因此可以不断往复迭代缩小求公约数的范围，直到余数c为0，此时的b值即为所求。
/**
最大公约数
辗转相除法
c = a % b, a > b
a = b
b = c
直到c = 0，b即为最大公约数
gcd: greatest common divisor
*/
int gcd(int a, int b) {
int c;
if (a < b) swap(a, b);
c = a % b;
while (c != 0) {
a = b;
b = c;
c = a % b;
}
return b;
}
递归形式
int gcd(int a, int b) {
return b == 0? a : gcd(b, a % b);
}
辗转相减法
辗转相减法，也叫尼考曼彻斯发。
有2个整数a、b，
- 如果a > b，则 a = a - b；
- 如果a < b，则 b = b - a；
- 如果a = b，则a或b即为两数的最大公约数；
- 如果a ≠ b，则回到步骤1执行；
如求27、15最大公约数过程：
a = 27, b = 15
- ∵a = 27 > b = 15 ∴a = a - b = 12；
- ∵a = 12 < b = 15 ∴b = b - a = 3；
- ∵a = 12 > b = 3 ∴a = a - b = 9；
- ∵a = 9 > b = 3 ∴a = a - b = 6；
- ∵a = 6 > b = 3 ∴a = a - b = 3；
- ∵a = 3 == b ∴a=3是原数对27、15的最大公约数；
int gcd(int a, int b) {
if (a == 0 || b == 0) return 0;
while (a != b) {
if (a > b) a -= b;
else b -= a;
}
return a;
}
最小公倍数
最小公倍数 = a * b / gcd(a, b), 其中，a、b不能为0，gcd(a, b)是a和b的最大公约数
当a或b为0时，最小公倍数=0
/*
最小公倍数 = a * b / 最大公约数
lcm: least common multiple
*/
int lcm(int a, int b) {
if (b == 0) return b;
else return a * b / gcd(a, b);
}
int main() {
int a, b;
cin >> a >> b;
if (a <= 0 || b <= 0) {
cerr << "invalid input" << endl;
return 0;
}
cout << lcm(a, b) << endl;
return 0;
}