1011辗转相除法的运用

解题思路:辗转相除法的本质是：两个数的最大公约数，是其中较小的那个数和两数相除余数的最大公约数，不断嵌套，当余数为零时，那个较大数就是最大公约数

最大公倍数：两数积/两数最大公约数，设m,n, m = d *a;n = d*b;lcm = m*n/d =a * b * d

注意事项:

参考代码:

#include<iostream>

using namespace std;

int main(){

int m,n,b,a,c;

long long gcd,lcm;

cin>>m>>n;

b = m % n;

a = m;

c = n;//备份m,n，后面算公倍数要使用

while(b!=0){

b = m % n;//辗转相除

m = n;

n = b;

}

gcd = m;

lcm = a*c/gcd;

cout<<gcd<<" "<<lcm;//注意格式

return 0;

}