找到给定数组中具有最小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 value）素数因素的数字，可以做更好的修剪。因为分解成本也是如此，例如，人们可能会尝试（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可能会产生反作用。