给定一个大小为 N 的三元组阵列，我们必须从每个三元组中选择一个数字，形成一个 N 大小的新阵列，使得新阵列中数字的 GCD 最大。

示例：一个三元组阵列，其中 N=3 -

[(70, 105, 42),
(35, 60, 210),
(36, 70, 420)]

所以如果我们从第一个元素中选择 105，从第二个元素中选择 210，从第三个元素中选择 420，我们得到的 GCD 为 105。这是最大可能的答案。

当我使用蛮力时，我超出了时间限制（因为有指数可能性检查）。我想不出在这里使用动态编程的方法，除此之外我不确定如何继续这个问题。

uj5u.com热心网友回复：

我认为您可以维护一个可能的 gcd 串列。如果第一个三元组是 (a0, a1, a2)，则从set(a0, a1, a2). 然后对于第二个三元组，(b0, b1, b2)您将每个元素的 gcd 与集合中的每个元素相结合。所以：(gcd(a0, b0), gcd(a0, b1), gcd(a0, b2), gcd(a1, b0), gcd(a1, b1), gcd(a1, b2), gcd(a2, b0), gcd(a2, b1), gcd(a2, b2))。等等。

在每个步骤中，您都可以洗掉集合中任何其他元素的元素。（虽然这样做可能不值得）。

一旦你处理了每一个三元组，你的集合中的最大值就是你的答案。

看起来这个集合可能会呈指数增长，但它受 K 的函式（阵列中任何三元组中的最大值）的限制：集合中的元素数永远不能大于所有三个元素的因子数任何三元组，对于所有 eps>0 都是 o(K^eps)，实际上会更小。例如，如果您的所有数字都小于 10 亿，则该集合永远不会大于 4032（任何小于 10 亿的数字的最大因子数是 1344，并且 4032 = 3*1344）。

这意味着该算法对所有 eps>0 执行 O(NK^eps) gcd 操作。