o（1）中最大的公因子？

注：這是不是詢問如何解決GCF在O（n）的o（1）中最大的公因子？

你有兩個整數，n和i。我們如何（在僞代碼中）在恆定時間內計算GCM(n, i)，其中n和i的域爲0 -> infinity？

我見過的唯一的解決方案使用遞歸或循環。如果可能的話，我希望能夠在一段時間內完成。

謝謝。

2017-04-26 Hatefiend

你爲什麼認爲這是可能的？似乎對我來說顯然不可能。順便問一下，你問了GCD，但寫了GCM - 我懷疑這是一個錯字。 –

可能的重複[什麼是找到兩個數字的GCD的最快方法？]（http://stackoverflow.com/questions/22281661/what-is-the-fastest-way-to-find-the-gcd-的兩個數字） –

嗯，從技術上講，這是可能的，是的 - 例如，通過創建預先計算的結果矩陣。但由於瘋狂的內存消耗，這是不實際的。

N.B .:這種方法有一個重要的先決條件：

n, i ∉ [0; ∞)，而是n, i ∈ [0; M], M ∈ [0; ∞) - 即取值範圍是任意大，但仍固定的。

否則，將n和i讀取到內存中的操作將是漸近線性的，使得即使在理論上也不可能是O(1)。

2017-04-26 18:41:30 hidefromkgb

謝謝。我有一種感覺，通過傳統手段是無法實現的。雖然有趣的想法！ – Hatefiend

它不一定是一個矩陣，你可以創建一個你需要的數字的所有因素的掩碼，並做兩個掩碼的「和」。這將是一個非常大的表格。 –

如果問題明確說明'i'，'n'的範圍是0到無窮大，這怎麼可能？你無法預先計算無限多的答案。 –

回答