WZOI-222最小公倍数

题目描述:

输入任一的自然数A, B, 求A , B的最小公倍数。

输入格式:

两个数，空格隔开

输出格式:

一个数，表示A、B的最小公倍数

样例输入:

3 5

样例输出:

15

提示:

使用辗转相除法求出A、B的最大公约数（也就是最大公因数）。

欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。计算公式gcd(a,b) = gcd(b,a mod b)。

最小公倍数 = 两个数之积 / 两者的最大公约数

A, B均为int范围的数。

时间限制: 1000ms
空间限制: 128MB

代码如下：
 

#include<bits/stdc++.h>
using namespace std;
int main(){
	unsigned long long a,b,r,a1,b1;
	cin>>a>>b;
	a1=a;
	b1=b;
	while(1){
		r=a%b;
		if(r==0){
			break;
		}
		a=b;
		b=r;
	}
	cout<<a1*b1/b;
	return 0;
}