注：これは、次の2つの整数、nとiを持ってo（1）の最も大きな共通因子ですか？
O（N）でGCFを解決する方法を求めていません。私たちはどのようにして（擬似コードで）GCM(n, i)を一定時間で計算できますか？nとiのドメインは0 -> infinityですか？
私が見た唯一の解決策は、再帰またはループを使用することです。それが可能であれば、私は一定の時間にそれをしたいと思います。
ありがとうございました。
技術的には、これは可能です。たとえば、事前計算された結果のマトリックスを作成します。しかし、これは非常識なメモリ消費のためにほとんど実用的ではありません。
N.B .:この方法は、重要な前提条件があります
n, i ∉ [0; ∞)を、むしろn, i ∈ [0; M], M ∈ [0; ∞) - すなわち、値の範囲が任意の大きさ、まだ固定されています。
そうでなければ、nとiをメモリに読み込む操作は漸近的に線形になり、理論的には不可能になります。O(1)
ありがとうございます。私は伝統的な手段ではそれができないと感じていました。面白いアイデア！ – Hatefiend
これは行列である必要はなく、必要な数のすべての要素のビットマスクを作成し、2つのビットマスクの 'と'を実行することができます。しかし、それは非常に大きなテーブルになります。 –
質問で明示的に 'i'、' n'の範囲が0から無限大までであると言うことができますか？無限に多くの答えを事前に計算することはできません。 –
なぜこれが可能だと思いますか？私には明らかに不可能だと思われる。ちなみに、あなたはGCDについて尋ねましたが、GCMを書いています - これはタイプミスだと思われます。 –
[2つの数字のGCDを見つける最速の方法は？]（http://stackoverflow.com/questions/22281661/what-is-the-fastest-way-to-find-the-gcd- 2桁の数字） –