求最大公约数常用的有两种方法,一是九章算术中的更相减损术:大数减小数直到相等,相等的数即最大公约数,该算法时间复杂度约为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);
}