1011: [编程入门]最大公约数与最小公倍数

解题思路:

求gcd要用辗转相除法，原理就不多赘述了；求lcm就用两数之积除去它们的gcd。

注意事项:

理解辗转相除法的原理就行。

参考代码:

#include <iostream>

using namespace std;

int gcd(int a, int b); //greatest common division
int lcm(int a, int b); //lease common multiple
int main() {
	int m = 0;
	int n = 0;
	cin >> m >> n;
	cout << gcd(m, n) << " " << lcm(m, n) << endl;
	return 0;
}
int gcd(int a, int b) {
	if(b > a) {
		swap(a, b); //确保a为较大数，b为较小数，方便计算
	}
	while(1) {
		int c = a % b; //c为余数，如果c是b的因数，则c是gcd
		if(b % c == 0) {
			return c;
		} else {
			a = b; //较小数是新的较大数
			b = c; //余数是新的较小数
		}
	}
}
int lcm(int a, int b) {
	int c = gcd(a, b);
	return a * b / c; //其实应该写成(a / c) * (b / c) * c方便理解
}