题解 | #求最小公倍数#

求最大公约数常用的有两种方法， 一是九章算术中的更相减损术：大数减小数直到相等，相等的数即最大公约数，该算法时间复杂度约为O(N)； 二是欧几里得的辗转相除法：大数除以小数取余数(相当于模运算)，直到余数为零时(也即模运算为零时)的除数(也即模数)就是最大公约数，该算法时间复杂度约为O(logN)。

求最小公倍数的方法：原始数据的乘积除以最大公约数。

#include<stdio.h>
int main(){
    int a,b;
    while(~scanf("%d %d",&a,&b)){
        if(a<b){a=a+b;b=a-b;a=a-b;}  //交换a,b大小
        int c=0,s=a*b;
        while(a%b){
            c=a%b;
            a=b;
            b=c;
        }printf("%d\n",s/b);
    }
}