コプライムサブアレイを見つける効率的なアプローチ

Question

アレイが与えられた場合、アレイのコインプライムサブアレイの数をO（N²）時間よりも長く見つけることは可能ですか？ Co-Prime配列は、すべての要素のGCDが1になるように、配列の連続したサブセットとして定義されます。

Answer 1

配列の最後に1つの要素を追加することを検討してください。ここで右端の位置があれば、その位置から追加した要素までのサブ配列がコプライムになるようにします。それが右端であるため、追加された要素で終わる短い配列はコプリムではありません。それはコプリムであるため、左に始まり新しい要素で終わるすべての配列はコプライム（co-prime）です。したがって、新しい要素で終わるコプライムサブアレイの数を計算しました。 O（n）の代わりにO（log n）のように右端の位置を効率的に見つけることができれば、O（n log n）のコプライムサブアレイの数を、時間。

右端の位置を見つけることができるようにするには、完全な配列を完全な2分木の葉として考え、その長さを2の累乗にするようにパディングします。各ノードで、そのノードの下にあるすべての要素のGCDを入力します。これは時間O（n）のボトムアップから行うことができます。配列内の連続したすべての区間は、ノードの下にある葉から間隔がくるように、サイズO（log n）のノードの集合でカバーすることができるため、区間のGCDを時間O（log n）として計算できます。

現在の要素との間でコニ係数サブアレイを形成する最も右の位置を見つけるには、現在の要素から始め、それが1であるかどうかを確認します。そうでない場合は、要素を左に見てGCDを取り出し、結果をスタックにプッシュします。結果が1の場合は終了し、そうでない場合は終了しますが、2つの要素のサブツリーが存在するかどうかを調べて、2つの要素を同時に追加できます。後続の各ステップで、検索しようとしているサブツリーのサイズを2倍にします。あなたはいつも好きなサイズの便利なサブツリーを見つけることはできませんが、すべての間隔をO（log n）サブツリーでカバーすることができるので、時間O（log n）のこのステップをたどるのに十分なことがよくあるでしょう。

現在、現在の要素の配列全体がコプライムでないか、またはコプライムであるセクションが見つかったが、必要以上に左に移動する可能性があります。スタックの一番上にある値は、GCDをそのスタックのすぐ下の値で、GCDをサブツリーの上部に置くことによって計算されました。それをスタックからポップし、その直下の値とサブツリーの右半分のGCDを取る。あなたがまだコプライムであれば、サブツリーの左半分は必要ありません。そうでなければ、あなたはそれを必要としましたが、おそらくすべてではありません。いずれの場合でも、時間O（log n）の中で最も右の一致を見つけるために継続することができます。

だから、私はあなたが時間の現在の要素を持つコインプライムサブアレイを形成することができると思う（おそらくいくつかの非常に厄介なプログラミングと）間違ったサブアレイの数を数えることができます時間O（NログN）

二つの例：

リスト1、3、5、7次のレベルは1,1であり、現在の要素が13である場合、ルートは1であるが、私は反対チェックしたがって、GCD（5,7,13）= GCD（3,5,7,13）= GCD（1,3,4,7,13）は、 = 1

リスト2,4,8,16次のレベル現在の数字が32の場合、16と照合してgcd（16,32）= 16！= 1を見つけたら、8と照合してそのGCD（8,32）を見つけます。 ）= 8とし、GCD（2,32）= 2でGCD = 1の拡張配列に区間がないことを確認します。