寻找最小公倍数问题解析
问题理解
给定一个长度为 nnn 的数组，我们需要找到所有数对 (ai,aj)(a_i, a_j)(ai ,aj ) 的最小公倍数（LCM）中的最大值。
数学背景
两个数 aaa 和 bbb 的最小公倍数可以通过它们的最大公约数（GCD）来计算：
LCM(a,b)=a×bGCD(a,b)\text{LCM}(a, b) = \frac{a \times b}{\text{GCD}(a, b)} LCM(a,b)=GCD(a,b)a×b
算法思路
1. 暴力枚举：由于 n≤500n \leq 500n≤500，我们可以枚举所有可能的数对 (i,j)(i, j)(i,j)，其中 i<ji < ji<j
2. 计算LCM：对于每对数，计算它们的LCM值
3. 记录最大值：在所有计算的LCM值中找出最大值
代码实现
算法分析
1. 时间复杂度：O(n2×log(max(ai)))O(n^2 \times \log(\max(a_i)))O(n2×log(max(ai )))
* 外层循环 nnn 次，内层循环 n−in-in−i 次，总共约 n(n−1)2\frac{n(n-1)}{2}2n(n−1) 次循环
* 每次循环调用 __gcd() 函数，其时间复杂度为 O(log(min(ai,aj)))O(\log(\min(a_i, a_j)))O(log(min(ai ,aj )))
2. 空间复杂度：O(n)O(n)O(n)，用于存储输入数组
优化考虑
虽然这是暴力解法，但由于 n≤500n \leq 500n≤500，最大循环次数约为 500×4992=124750\frac{500 \times 499}{2} = 1247502500×499 =124750 次，加上GCD计算，总操作次数在可接受范围内。
注意事项
* 使用 __gcd() 函数需要包含 <algorithm> 或 <bits/stdc++.h>
* 如果使用其他编译器，可以自己实现GCD函数：
* 题目保证 1≤ai≤5001 \leq a_i \leq 5001≤ai ≤500，因此计算 ai×aja_i \times a_jai ×aj 最大为 250000250000250000，不会超出 int 范围
