11

いくつかの非負の数があります。最大公約数のペアを見つけたいと思います。実際、この最大値はペアよりも重要です。たとえば、次の場合：

2 4 5 15

gcd（2,4）= 2

gcd（2,5）= 1

gcd（2,15）= 1

gcd（4,5）= 1

gcd（4,15）= 1

gcd（5,15）= 5

答えは5です。

4

7 に答える 7

5

ユークリッドアルゴリズムを使用して、2つの数値のGCDを見つけることができます。

while (b != 0) 
{
    int m = a % b;
    a = b;
    b = m;
}
return a;
于 2010-09-08T13:23:08.913 に答える
4

明白なアルゴリズムの代替が必要な場合は、数値が制限された範囲内にあり、十分なメモリがあると仮定すると、O（N ^ 2）時間を超えることができます。Nは値の数です。

  • 小さな整数型の配列を作成し、1を最大入力にインデックス付けします。O（1）
  • 値ごとに、数値の係数であるインデックスのすべての要素のカウントをインクリメントします（ラップアラウンドしないように注意してください）。オン）。
  • 配列の最後から始めて、2以上の値が見つかるまでスキャンバックします。O（1）

それはあなたに最大公約数を教えてくれますが、どのペアがそれを生み出したかは教えてくれません。入力例の場合、計算された配列は次のようになります。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
4 2 1 1 2 0 0 0 0 0  0  0  0  0  1

あなたが処理しなければならない入力に対して、これが実際にもっと速いかどうかはわかりません。関係する一定の要因は大きいです：あなたの値の限界とその限界内の値を因数分解する時間。

各値を因数分解する必要はありません。メモ化や事前に生成された素数のリストを使用できます。これは、因数分解を記憶している場合、配列は必要ないという考えを私に与えます。

  • intの空のセットと、これまでで最高の値1を作成します。
  • 入力整数ごとに：
    • これまでのベスト以下の場合は、続行します。
    • セットに含まれているかどうかを確認してください。その場合、best-so-far = max（best-so-far、this-value）、続行します。そうでない場合：
      • セットに追加する
      • そのすべての要因について繰り返します（これまでのところよりも大きい）。

セット内の追加/ルックアップはO（log N）である可能性がありますが、使用するデータ構造によって異なります。各値にはO（f（k））係数があります。ここで、kは最大値であり、関数fが何であるかを思い出せません。

セット内で値に遭遇するとすぐに値を終了する理由は、2つの入力値の共通因子である数値を見つけたためです。因数分解を続けると、そのような数は少なくなりますが、これは面白くありません。

より大きな要因に対して繰り返すのが最善の方法かどうかはよくわかりません。実際には、バランスをとる必要があると思います。順序付けられた要素を生成するのは面倒なので、降順で完全に実行したくはありませんが、実際にすべての要素を見つけたくはありません。

O（N ^ 2）の領域でも、ユークリッドの互除法の使用を打ち負かすことができるかもしれません。

各数値を完全に因数分解し、素数の指数のシーケンスとして格納します（たとえば、2は{1}、4は{2}、5は{0、0、1}、15は{0、1、1}） 。次に、各インデックスの最小値を取得し、それらを乗算して戻すことにより、gcd（a、b）を計算できます。これが平均してEuclidより速いかどうかはわかりませんが、速いかもしれません。明らかに、より多くのメモリを使用します。

于 2010-09-08T15:12:23.023 に答える
3

私が考えることができる最適化は

1）最も素因数が最も多く、したがって最も共有されている素因数（したがって最も高いGCD）を持つ可能性が高いため、2つの最大数から始めます。

2）他のペアのGCDを計算するときに、現在の最大GCDを下回った場合は、ユークリッドアルゴリズムループを停止できます。

私の頭の上から、各ペアを個別に計算しようとせずに（そして上記のように少し最適化することなく）ペアの最大のGCDを計算する方法を考えることはできません。

免責事項：私はこれまでこの問題を見たことがなく、上記は頭から離れています。もっと良い方法があるかもしれませんし、私は間違っているかもしれません。誰かが望むなら、私は私の考えをもっと詳しく話し合うことができてうれしいです。:)

于 2010-09-08T14:34:04.913 に答える
1

O(n log n)一般に、この問題に対する解決策はありません。実際、最悪のケースはO(n^2)リスト内のアイテムの数です。次の一連の数字を検討してください。

2^20 3^13 5^9 7^2*11^4 7^4*11^3

最後の2つのGCDのみが1より大きいですが、GCDを見てそれを知る唯一の方法は、すべてのペアを試して、そのうちの1つが1より大きいことに気付くことです。

したがって、大きなGCDをすでに見つけたときに不必要な作業を行わないようにするために、おそらくいくつかの巧妙な最適化を使用して、退屈なブルートフォーストライエブリペアアプローチに固執しています（何かを見逃さないようにしながら） ）。

于 2010-09-08T14:53:17.123 に答える
1

いくつかの制約があります。たとえば、配列内の数値が1-1e7などの特定の範囲内にある場合、O（NlogN）/ O（MAX * logMAX）で実行できます。ここで、MAXはAで可能な最大値です。

ふるいアルゴリズムから発想を得て、ハッカーランクチャレンジでそれに出くわしました-そこでは2つのアレイに対して行われます。彼らの社説をチェックしてください。

  • find min（A）およびmax（A）-O（N）
    は、O（1）ルックアップのために、指定された範囲にAのどの要素が表示されるかをマークするバイナリマスクを作成します。構築するO（N）; O（MAX_RANGE）ストレージ。
  • 範囲内のすべての数値aに対して（min（A）、max（A））：
    for aa = a; aa <max（A）; aa + = a：
    • Aのaaの場合、aaのカウンターをインクリメントし、現在のmax_gcdと比較します。counter> = 2の場合（つまり、aaで割り切れる2つの数値があります）。
    • 各GCD候補の上位2つの候補を保存します。
    • 現在のmax_gcdよりも小さい要素を無視することもできます。

前の回答：それでもO（N ^ 2）-配列をソートします。不要な比較の一部を排除する必要があります。

max_gcd = 1
# assuming you want pairs of distinct elements.
sort(a) # assume in place
for ii = n - 1: -1 : 0 do
    if a[ii] <= max_gcd
        break
    for jj = ii - 1 : -1 :0 do
        if a[jj] <= max_gcd 
            break
        current_gcd = GCD(a[ii], a[jj])
        if current_gcd > max_gcd:
            max_gcd = current_gcd

これにより、不要な計算を節約できます。

于 2017-07-18T07:38:25.277 に答える
0

擬似コード

function getGcdMax(array[])

    arrayUB=upperbound(array)
    if (arrayUB<1)
        error
    pointerA=0
    pointerB=1

    gcdMax=0

    do
        gcdMax=MAX(gcdMax,gcd(array[pointera],array[pointerb]))
        pointerB++
        if (pointerB>arrayUB)
            pointerA++
            pointerB=pointerA+1
    until (pointerB>arrayUB)

    return gcdMax
于 2010-09-08T14:16:10.913 に答える
0

O（n）を取る解決策があります：

私たちの数をa_i。まず、を計算しm=a_0*a_1*a_2*...ます。数値a_iごとに、を計算しgcd(m/a_i, a_i)ます。探している数は、これらの値の最大値です。

これが常に正しいことを証明したわけではありませんが、あなたの例では、次のように機能します。

m=2*4*5*15=600,

max(gcd(m/2,2), gcd(m/4,4), gcd(m/5,5), gcd(m/15,15))=max(2, 2, 5, 5)=5

注：これは正しくありません。数値a_iに2回繰り返される因数があり、p_j他の2つの数値にもこの因数が含まれている場合、 。p_jの誤った結果が得られます。たとえば、セットの場合、の代わりに答えとして取得します。p_j^2p_j3, 5, 15, 25255

ただし、これを使用して、数値をすばやく除外することはできます。たとえば、上記の場合、25を決定したら、最初にで徹底的な検索を実行しa_3=25てgcd(a_3, a_i)実際の最大値を見つけ、次に、以下の値を5除外できます（上記の例では、これによりすべてが除外されます）その他）。gcd(m/a_i, a_i), i!=35

明確化と正当化のために追加：

これが機能する理由を確認するには、すべてのにgcd(a_i, a_j)分割されることに注意してください。gcd(m/a_i, a_i)j!=i

、、gcd(m/a_i, a_i)と呼びましょう。私が上で言ったことは、であり、整数です。は明らかです。したがって、 gcd操作では、すべてのの上限を取得します。g_imax(gcd(a_i, a_j),j=1..n, j!=i)r_ig_i=x_i*r_ix_ir_i <= g_inr_ii

上記の主張はあまり明白ではありません。それが真実である理由を確認するためにもう少し深く調べてみましょう。とのgcdはa_i、と（定義上）a_jの両方に現れるすべての素因数の積です。ここで、別の数値を掛けます。とのgcdは、に等しいか、またはその倍数です。これは、のすべての素因数と、によって寄与されるいくつかの素因数が含まれているためです。これは、の因数分解にも含まれる場合があります。実は、と思います。しかし、これを利用する方法がわかりません。:)a_ia_ja_jba_ib*a_jgcd(a_i, a_j)b*a_ja_jba_igcd(a_i, b*a_j)=gcd(a_i/gcd(a_i, a_j), b)*gcd(a_i, a_j)

とにかく、私たちの構造でm/a_iは、すべての積を計算するためのショートカットにすぎません。a_jここで、j=1..1, j!=i。結果として、gcd(m/a_i, a_i)はすべてgcd(a_i, a_j)を要因として含みます。したがって、明らかに、これらの個々のgcd結果の最大値は除算されg_iます。

さて、g_i最大公約数は私たちにとって特に興味深いものです。それは最大公約数自体（x_i1の場合）、または1になるための適切な候補のいずれかです。これを行うには、別のn-1gcd操作を実行し、r_i明示的に計算します。次に、候補としてg_j以下をすべて削除します。r_i他に候補者がいなければ、完了です。そうでない場合は、次に大きいg_kを取得し、を計算しr_kます。の場合r_k <= r_i、を削除g_kし、別のを繰り返しg_k'ます。の場合r_k > r_i、残りのを除外してg_j <= r_k繰り返します。

このアルゴリズムをO（n ^ 2）で実行する数セットを構築することは可能だと思いますが（何かを除外できなかった場合）、乱数セットでは、候補者。

于 2010-09-08T17:15:13.583 に答える