求 n 个数的最小公倍数(详解版)
你的好朋友小明最近在学习最小公倍数的知识，他妈妈给他出了100题，每一题都有n(2≤n≤20)个数，要小明求出这n个数的最小公倍数。小明现在想快点出去玩，于是想到会编程的你，能否设计一个程序，让他输入题目n个数就可以得到答案？快来帮帮小明吧！
输入格式
第一行一个整数 n (2≤n≤20)。
第二行 n 个整数。
输出格式
一个整数，表示最小公倍数，数据保证答案不超过int范围。
输出时每行末尾的多余空格，不影响答案正确性
输入/输出例子1
输入：
5
2 4 6 8 10
输出：
120
浅说：这道题如果是道数学的话比较容易，但代码实现的话不容易想到，下面对这道题的思路和样例进行了详细地解析，方便大家更好的理解~ 完整代码在最下面~
核心代码片段
for(int j = n - 1; j > 0; j--) {
for(int i = a[j - 1]; i > 0; i--) {
if(a[j] % i == 0 && a[j - 1] % i == 0) {
a[j - 1] = a[j] * a[j - 1] / i;
break;
}
}
}代码的作用
这段代码的目的是计算数组中所有数的最小公倍数（LCM）。它的核心思想是：
-
从数组的末尾开始，依次计算相邻两个数的最小公倍数。
-
将计算得到的最小公倍数赋值给前一个数，然后继续向前计算。
-
最终，数组的第一个元素（
a[0]）就是所有数的最小公倍数。
代码的详细逻辑
for(int j = n - 1; j > 0; j--)- 从数组的最后一个元素开始，向前遍历到第二个元素（j 从 n-1 到 1）。
- 每次循环处理 a[j] 和 a[j-1] 两个数。
for(int i = a[j - 1]; i > 0; i--)- 从 a[j-1] 开始递减，寻找 a[j] 和 a[j-1] 的最大公约数（GCD）。
- i 是可能的公约数，从大到小遍历。
if(a[j] % i == 0 && a[j - 1] % i == 0)-
如果
i能同时整除a[j]和a[j-1]，则i是它们的公约数。 -
由于
i是从大到小遍历的，第一个满足条件的i就是最大公约数（GCD）。
a[j - 1] = a[j] * a[j - 1] / i;-
利用公式 LCM(a,b) = GCD(a,b) / a×b 计算最小公倍数。
-
将计算得到的最小公倍数赋值给
a[j-1]。
break;-
找到最大公约数并计算最小公倍数后，跳出内层循环，继续处理下一对数。
举例说明
假设输入数组为 a = [2, 4, 6, 8, 10]，n = 5。
第一次外层循环（j = 4）：
-
当前数：
a[j] = 10，a[j-1] = 8。 -
内层循环从
i = 8开始递减：-
i = 8：检查10 % 8 == 2，不满足。 -
i = 7：检查10 % 7 == 3，不满足。 -
i = 6：检查10 % 6 == 4，不满足。 -
i = 5：检查10 % 5 == 0且8 % 5 == 3，不满足。 -
i = 4：检查10 % 4 == 2，不满足。 -
i = 3：检查10 % 3 == 1，不满足。 -
i = 2：检查10 % 2 == 0且8 % 2 == 0，满足。-
计算最小公倍数：
a[j-1] = (10 * 8) / 2 = 40。 -
更新数组：
a = [2, 4, 6, 40, 10]。 -
跳出内层循环。
-
-
第二次外层循环（j = 3）：
-
当前数：
a[j] = 40，a[j-1] = 6。 -
内层循环从
i = 6开始递减：-
i = 6：检查40 % 6 == 4，不满足。 -
i = 5：检查40 % 5 == 0且6 % 5 == 1，不满足。 -
i = 4：检查40 % 4 == 0且6 % 4 == 2，不满足。 -
i = 3：检查40 % 3 == 1，不满足。 -
i = 2：检查40 % 2 == 0且6 % 2 == 0，满足。-
计算最小公倍数：
a[j-1] = (40 * 6) / 2 = 120。 -
更新数组：
a = [2, 4, 120, 40, 10]。 -
跳出内层循环。
-
-
第三次外层循环（j = 2）：
-
当前数：
a[j] = 120，a[j-1] = 4。 -
内层循环从
i = 4开始递减：-
i = 4：检查120 % 4 == 0且4 % 4 == 0，满足。-
计算最小公倍数：
a[j-1] = (120 * 4) / 4 = 120。 -
更新数组：
a = [2, 120, 120, 40, 10]。 -
跳出内层循环
-
-
第四次外层循环（j = 1）：
-
当前数：
a[j] = 120，a[j-1] = 2。 -
内层循环从
i = 2开始递减：-
i = 2：检查120 % 2 == 0且2 % 2 == 0，满足。-
计算最小公倍数：
a[j-1] = (120 * 2) / 2 = 120。 -
更新数组：
a = [120, 120, 120, 40, 10]。 -
跳出内层循环。
-
-
最终结果
-
a[0] = 120，输出120。
完整代码
#include<bits/stdc++.h>
using namespace std;
int n,a[25];
int main(){
cin>>n;
for(int i = 0;i < n;i++){
cin>>a[i];
}
sort(a,a + n);
for(int i = n - 1;i > 0;i--){
for(int j = a[i - 1];j > 0;j--){
if(a[i] % j == 0 && a[i - 1] % j == 0){
a[i - 1] = a[i] * a[i - 1] / j;
break;
}
}
}
cout<<a[0];
return 0;
}
创造不易，如果对您有所帮助，请一键三连哦～你的支持是我继续创造的动力源泉～