查找共素數子陣列的有效方法

Question

給定一個數組，是否有可能找到比O（N 2）時間更好的數組的共素數子陣列的數目？共素陣列被定義爲數組的一個連續子集，因此所有元素的GCD都是1.

Answer 1

考慮在數組的末尾添加一個元素。現在找到最右邊的位置（如果有的話），使得從該位置到剛剛添加的元素的子數組是共素數。由於它是最右邊的，所以添加元素結束的更短陣列是共素。由於它是共素數，每個從左到右以新元素結束的數組都是共素數。所以你已經計算出以新元素結束的共素數子數組的數量。如果你能夠有效地找到最右邊的位置 - 例如在O（log n）而不是O（n）中 - 那麼你可以通過將數組中的一個元素擴展到O（n log n）來計算共素數子數組的數量一次。

爲了使找到最右邊的位置成爲可能，將完整數組視爲完整二叉樹的葉子，填充以使其長度爲2的冪。在每個節點上放置該節點下的所有元素的GCD - 您可以在時間O（n）的底部向上執行此操作。數組中的每個連續間隔都可以由大小爲O（log n）的節點集合覆蓋，這樣間隔由節點下面的葉組成，因此可以計算間隔的GCD是時間O（log n）。

要找到與當前元素形成共素數子陣的最右邊位置，請從當前元素開始，檢查它是否爲1。如果是，則完成。如果沒有，請查看其左側的元素，以此作爲GCD，並將結果推送到堆棧中。如果結果爲1，則結束，如果不完成，則執行相同操作，但查看是否存在可用於一次添加2個元素的2個元素的子樹。在接下來的每一步中，您都會嘗試查找子樹的兩倍大小。你不會總是找到一個你想要的大小的方便的子樹，但是因爲每個時間間隔都可以被O（log n）子樹覆蓋，所以你應該經常足夠幸運地經歷這個時間O（log n）。

現在您已經發現整個數組對於當前元素不是共素數，或者您找到了一個共素數的區域，但可能會比它需要的更遠。堆棧頂部的值是通過將堆棧下面的GCD值和子樹頂部的GCD值計算出來的。將它從堆棧中彈出並將剛剛在它下面的值和子樹的右半邊的GCD取出。如果你仍然是共素，那麼你不需要子樹的左半部分。如果沒有，那麼你需要它，但也許不是全部。無論哪種情況，您都可以繼續在時間O（log n）中找到最右邊的匹配項。

所以我認爲你可以在時間O（log n）中找到與當前元素形成一個共素數子陣的最右邊的位置（不可否認地有一些非常複雜的編程），所以你可以計算互素子數組的數目時間爲O（n log n）的

兩個例子：

列表1，3，5，7，下一個級別是1,1和根爲1。如果當前元素是13然後我對證因此，我立即知道GCD（5,7,13）= GCD（3,5,7,13）= GCD（1,3,4,7,13），並且發現gcd（7,13）= 1。 = 1.

列表2,4,8,16。下一列夫el是2,8，根是2.如果當前的數字是32，那麼我檢查16，發現gcd（16,32）= 16！= 1，然後我檢查8，發現GCD（8,32 ）= 8，然後檢查2，發現GCD（2,32）= 2，因此在GCD = 1的擴展陣列中沒有間隔。