#题目描述
求两个数的最大公约数和最小公倍数
提示:两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数(Greatest Common Divisor)缩写为GCD。
gcd(a,b) = gcd(b,a mod b) (不妨设a>b 且r=a mod b ,r不为0)
#输入格式
输入只有一行,为两个正整数m,n(0<m,n<109)。
提示:使用 long long int 类型
#输出格式
输出只有二行。
第一行m和n的最大公约数。
第二行m和n的最小公倍数。
#样例输入
3 6
#样例输出
3
6
#include <iostream>
using namespace std;
int main() {
long long int m = 1;long long int n=1;
cin >> m >> n;
int gcd, lcm;
int a = 1; int b = 1; int c = 1;
if (m > n) { a = m; b = n; }
else { a = n; b = m; }
while (1) {
if (a % b == 0) break;
c = b;
b = a % b;
a = c;
}
gcd = b; lcm = m * n / gcd;
cout << gcd << endl << endl << lcm;
return 0;
}