题解 | #小乐乐与欧几里得#

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

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

本题数据偏大，选择时间效率更高的辗转相除法更好，第一次提交没通过，发现一组测试用例的输出竟然是负数，一猜肯定是溢出了，然后把数据类型声明改为long long型：

#include<stdio.h>
int main(){
    long long a,b,comax,comin,k;
    scanf("%lld %lld",&a,&b);
    k=a*b;
    while(a&&b){
        if(a>b) a %=b;
        else b %= a;
    }
    comax=a>b?a:b;
    comin=k/comax;
    printf("%lld\n",comax+comin);
}