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

#include <stdio.h>
long long test1(long long a, long long b)    //使用迭代方法实现欧几里得算法求最大公约数
{
    if (a == 0 || b == 0)
    {
        return 0;
    }
    long long r = a % b;
    while (r != 0)
    {
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}
long long test2(long long a, long long b)    //使用递归方法实现欧几里得算法求最大公约数
{
    if (a == 0 || b == 0)
    {
        return 0;
    }
    else if (a % b == 0)
        return b;
    else
    {
        long long r = a % b;
        return test2(b, r);
    }
}
int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    long long result1 = test2(a, b);
    long long result2 = a / result1 * b / result1 * result1;        //不要为了这部分性能而影响代码可读性
    printf("%ld", result1 + result2);
}

1.显然不可能暴力解，10^8级数据肯定会爆炸

2.考虑到两个十亿以内的数的最小公倍数可能会很大，所以选择long long，2^63估算上限在10^18数量级，不会溢出

3.辗转相除法/欧几里得算法求最大公约数的原理：https://www.bilibili.com/video/BV1my4y1z7Zn/?spm_id_from=333.337.search-card.all.click&vd_source=441d2aa2c4bb2a4eccbf0d3f0f77398d

原理证明的基本思路：证(a,b)的公因数一定是r的公因数，证(b,r)的公因数也一定是a的公因数，所以(a,b)的公因数一定是(b,r)的公因数，(b,r)的公因数也一定是(a,b)的公因数，所以两者的公因数完全相同，所以最大公因数也相同。

4.可以采用递归或者迭代的方法来实现，此外，可以不用考虑a=0或b=0的情况，题目已说明是正整数。但是要了解，输入0会崩溃。