牛客竞赛题库（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，直至余数为零结束。
这里我将代码运行方式形象地写在纸上，方便理解递归函数以及辗转相除法在代码中的运行。
求最小公倍数的话，只需要两个正整数相乘除以最小公倍数即可，这里我们需要做一个小小的调整，要先除后乘，如果先相乘的话可能会溢出，超过该数据类型的范围，所以我们就先让一个正整数除以最小公倍数然后再乘以另一个正整数，即可完成该题目。
牛客竞赛题库（C语言） 文章被收录于专栏
这是我对题库写的代码以及分析，由易到难，我会坚持把它写完，可能有些粗糙，专栏免费，不想看可以划走。
正浩创新EcoFlow公司福利 68人发布
查看7道真题和解析
投递BOSS直聘等公司6个岗位