牛客竞赛题库（NC6710）

#include<stdio.h>

unsigned long long gcd(unsigned long long a, unsigned long long b)
{
    return b == 0 ? a : gcd(b, a % b);
}

int main()
{
    unsigned long long a, b;
    scanf("%llu %llu", &a, &b);
    unsigned long long result = a / gcd(a, b) * b;
    printf("%llu\n", result);
    return 0;
}

这里我们写一个关于辗转相除法的函数来计算两个正整数的最大公约数。

公式基本原理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。

该函数代码运行方式：当b为0时，此时的a就是最大公约数，直接返回a，否则递归调用gcd函数，将b作为新的a，a%b作为新的b，直至余数为零结束。

这里我将代码运行方式形象地写在纸上，方便理解递归函数以及辗转相除法在代码中的运行。

求最小公倍数的话，只需要两个正整数相乘除以最小公倍数即可，这里我们需要做一个小小的调整，要先除后乘，如果先相乘的话可能会溢出，超过该数据类型的范围，所以我们就先让一个正整数除以最小公倍数然后再乘以另一个正整数，即可完成该题目。