一、题干
牛客网链接
二、题解
1. 辗转相除法
辗转相除法可求出两数的最大公约数，再由公式 最小公倍数 = 两数之积 / 最大公约数 求出最小公倍数。
//辗转相除法求最大公约数、最小公倍数 int main() { long long n = 0; long long m = 0; //输入两个数 scanf("%lld %lld", &n, &m); /*因为求最大公约数和最小公倍数都需要用到m、n，且辗转相除的过程会改编n、m的值， 故再创建两个变量n2、m2，把m和n的值拷贝一份再做运算*/ long long m2 = m; long long n2 = n; long long r = 0; //最大公约数 while (r = n2 % m2) { n2 = m2; m2 = r; //注意：m2才是所求的最大公约数的结果，而不是r } //最小公倍数 == m*n/最大公约数 printf("%lld", m * n / m2 + m2); //直接求最大公约数和最小公倍数的和 return 0; }
注意：不需要比较m和n两数的大小再计算。
2. 试除法
设置变量max代表最大公约数，变量min代表最小公倍数。
核心思路为，初始化max与输入的两数中更小的数相等；初始化min与输入两数中更大的数相等。
由最大公约数的规则，max能同时被两数除尽，且为满足条件的数中的最大值。这样一来，只需要让max不断自减，当max自减到恰好可以同时被两数除尽。这时候的max就是最大公约数。
同样，由最小公倍数的规则，min是两数的倍数，即min分别除以两数都能除尽，且为满足条件的最小值。这只需让min不断自增，一个一个向上走，直到恰好满足条件即可。
根据这样的思路，我们能总结出以下的算法：
int main() { int n = 0; int m = 0; scanf("%d %d", &n ,&m); int max = (n>m?m:n);//假设最大公约数，是n和m的较小值 //求最大公约数 while(1) { if(n % max == 0 && m % max == 0) { break; } max--; //max从m与n中的较小值开始不断自减，挨个检查是否满足条件。一旦满足就跳出 } int min = (n>m?n:m);//假设最小公倍数，是n和m的较大值 //求最小公倍数 while(1) { if(min % n == 0 && min % m == 0) break; min++; //思路同上，挨个检查 } printf("%d\n", max+min); //回到题干，题干要求的是求min和max的和 return 0; }
三、方法总结
1. 辗转相除法最大公约数
虽然上面介绍了用辗转相除法求最小公倍数的操作，但本质上辗转相除法在此是求最大公约数的。因此我们把它拿出来单独强调。
//辗转相除法求最大公约数 int main(){ int m,n; int tmp = 0; scanf("%d %d",m,n); while(tmp = m % n){ m = n; n = tmp; } printf(最大公约数是："%d",n); //注意，最后的n（也就是模数，右边的那个数）才是要求的最大公约数 }
最小公倍数 == 两数相乘再除以其最大公约数。
2. 迭乘法求最小公倍数
迭乘法的思路是这样的：
由公倍数的定义出发，如果一个数k是a和b的公倍数，那么k可以表示成 a*i 或 b*j 。转换成编程语言表达，即：
//若k为a和b的最小公倍数，则有： k == a*i k == b*j //也就是说，当(a*i) % b == 0时，k是最小公倍数
编写成完整代码，即：
//迭乘法求最小公倍数 int main(){ int a = 0; int b = 0; scanf("%d %d", &a, &b); //输入两个数 int i = 1; while((a*i) % b != 0){ i++; } printf("最小公倍数是：%d\n", a * i); //最小公倍数：i*a return 0; }
3. 试除法求最大公约数与最小公倍数
和上面提到过的试除法思路相同，就是挨个试。比如要求20和30的最大公约数，那就从20开始挨个往下检查，看看19能不能同时被20和30整除；19不符合条件再往下看18、17、16…直到找到符合条件的。求最小公倍数也一样，就是挨个往上试，总能找到满足条件的，再输出就好了。
确实，试除法的效率相对较低。
//最大公约数 int main() { int n = 0; int m = 0; scanf("%d %d", &n ,&m); int max = (n>m?m:n);//假设最大公约数，是n和m的较小值 //求最大公约数 while(1) { if(n % max == 0 && m % max == 0) { break; } max--; //max从m与n中的较小值开始不断自减，挨个检查是否满足条件。一旦满足就跳出 } printf("最大公约数是 %d",max); return 0; }
//最小公倍数 int main(){ int n = 0; int m = 0; scanf("%d %d", &n ,&m); int min = (n>m?n:m); //求最小公倍数 while(1) { if(min % n == 0 && min % m == 0) break; min++; } printf("最小公倍数是 %d", min); return 0; }
