笔记
- a 和 b 的最大公约数 等价于 b 与 a mod b 的最大公约数
- 最小公倍数等于 a * b / 最大公约数
代码
#include<iostream>
using namespace std;
int GCD(int a, int b) {
if(b == 0) return a;
else return GCD(b, a % b); //不断将(a,b) 变为 (b, a mod b)
}
int main() {
int a, b;
cin>>a>>b;
int k = GCD(a,b);
cout<<a / k * b <<" "<<k; //先除后乘,减少计算量
return 0;
}