寻找最小公倍数问题解析

问题理解

给定一个长度为 $n$ 的数组，我们需要找到所有数对 $(a_i, a_j)$ 的最小公倍数（LCM）中的最大值。

数学背景

两个数 $a$ 和 $b$ 的最小公倍数可以通过它们的最大公约数（GCD）来计算：

$$\text{LCM}(a, b) = \frac{a \times b}{\text{GCD}(a, b)}$$

算法思路

1. 暴力枚举：由于 $n \leq 500$，我们可以枚举所有可能的数对 $(i, j)$，其中 $i < j$
2. 计算LCM：对于每对数，计算它们的LCM值
3. 记录最大值：在所有计算的LCM值中找出最大值

代码实现

#include <bits/stdc++.h>  // 包含常用标准库
using namespace std;

int a[510];  // 存储输入数组，最大长度500

int main(){
    int n;  // 数组长度
    cin >> n;  // 读取数组长度
    
    // 读取数组元素
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    
    int maxx = 0;  // 记录最大LCM值
    
    // 枚举所有数对 (i, j)，其中 i < j
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            // 计算a[i]和a[j]的LCM
            // __gcd()是GCC内置函数，计算最大公约数
            int lcm = a[i] * a[j] / __gcd(a[i], a[j]);
            
            // 更新最大值
            maxx = max(maxx, lcm);
        }
    }
    
    cout << maxx;  // 输出最大LCM值
    return 0;  // 程序正常结束
}

算法分析

1. 时间复杂度：$O(n^2 \times \log(\max(a_i)))$
   • 外层循环 $n$ 次，内层循环 $n-i$ 次，总共约 $\frac{n(n-1)}{2}$ 次循环
   • 每次循环调用 __gcd() 函数，其时间复杂度为 $O(\log(\min(a_i, a_j)))$
2. 空间复杂度：$O(n)$，用于存储输入数组

优化考虑

虽然这是暴力解法，但由于 $n \leq 500$，最大循环次数约为 $\frac{500 \times 499}{2} = 124750$ 次，加上GCD计算，总操作次数在可接受范围内。

注意事项

• 使用 __gcd() 函数需要包含 <algorithm> 或 <bits/stdc++.h>
• 如果使用其他编译器，可以自己实现GCD函数：

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

• 题目保证 $1 \leq a_i \leq 500$，因此计算 $a_i \times a_j$ 最大为 $250000$，不会超出 int 范围