找到三胞胎数组的最大 GCD
find maximum GCD of an array of triplets
给你一个大小为N的三元组数组，我们必须从每个三元组中选择一个数字，形成一个新的N大小数组，使得新数组中数字的GCD最大。
示例：
N=3 -
的三元组数组
[(70, 105, 42),
(35, 60, 210),
(36, 70, 420)]
因此，如果我们从第一个元素中选择 105，从第二个元素中选择 210，从第三个元素中选择 420，我们将得到 105 的 GCD。这是最大可能的答案。
当我使用蛮力时，我超过了时间限制（因为有指数可能性要检查）。
我想不出在这里使用动态规划的方法，除此之外我不确定如何继续这个问题。
我认为您可以维护一个可能的 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 操作。
给你一个大小为N的三元组数组，我们必须从每个三元组中选择一个数字，形成一个新的N大小数组，使得新数组中数字的GCD最大。
示例： N=3 -
的三元组数组[(70, 105, 42),
(35, 60, 210),
(36, 70, 420)]
因此，如果我们从第一个元素中选择 105，从第二个元素中选择 210，从第三个元素中选择 420，我们将得到 105 的 GCD。这是最大可能的答案。
当我使用蛮力时，我超过了时间限制（因为有指数可能性要检查）。 我想不出在这里使用动态规划的方法，除此之外我不确定如何继续这个问题。
我认为您可以维护一个可能的 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 操作。