我想你可以保留一份可能的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(數組中任何三元組的最大值)的函數:集合中的元素數永遠不能大于任何三元組中所有三個元素的因子數,即o(K^eps)表示所有eps>0,實際上會更小。例如,如果您的所有數字都小于10億,則集合將永遠不會大于4032(小于10億的任何數字的最大因子數為1344,4032=3*1344)。 這意味著該算法對所有大于0的eps執行O(NK^eps)gcd操作。