給定一個大小為 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 操作。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/409385.html
標籤：
上一篇：generateKeycpp函式