arrays - 在给定数组中查找具有最小 LCM 值的对

Question

我最近在竞争性编程竞赛中遇到了一个问题。给定一个整数数组，找出 LCM 值最小的一对数组元素的索引。

我知道有一个天真的双循环 O(n^2) 解决方案，但正如预期的那样，它给出了时间限制异常。我听说动态规划用于优化蛮力方法，但我不知道如何将这个问题划分为子问题，以便有一个最佳的子结构。

我能得到任何方向来使用 DP 解决这个问题吗？或者有什么更好的方法吗？谢谢。

Answer 1

(假设为正数。)

最小的 LCM 可能源于最小的元素，因此要修剪尝试值，可以对数组进行排序。

int[] v = { ... };

int minLCM = Integer.MAX_VALUE;
int bestVi = -1;
int bestVj = -1;
Arrays.sort(v);
for (int i = 0; i < v.length; ++i) {
    int vi = v[i];
    //                                  _____________
    for (int j = i + 1; j < v.length && v[j] < minLCM; ++j) {
        int vj = v[j];
        int lcm = lcm(vi, vj);
        if (lcm < minLcm) {
            minLCM = lcm;
            bestVi = vi;
            bestVj = vj;
        }
    }
}

修剪:

lcm(vi, vj) >= vi
lcm(vi, vj) >= vj
(lcm(vi, vj) <= vi*vj

这种修剪只能在 for-j 循环中完成，因为 vj >= vi。

如果您有一个(至多 ²log 值)主要因素列表，而不是一个数字，则可以进行更好的修剪。由于分解成本也很高，例如可以尝试 (2, 3, 5, 7)。

更好的循环也可以通过替换两个嵌套循环来实现，这样最小的 (vi, vj) ​​先出现。上面的 (v0, v100) 在 (v1, v2) 之前。循环递增的 i+j。

i j
0 1
0 2
0 3
1 2
0 4
1 3
0 5
1 4
2 3
...

(使用对角线的循环计数器的数学是一个很好的难题。真的应该完成。)

尽管仍然是 O(n²) 这可能有效。

有时编程语言也很重要，在这些情况下通常会看到 C 语言的贡献。在这种情况下，使用 Ruby 可能适得其反。