algorithm - 寻找互质子阵列的有效方法

Question

给定一个数组，是否有可能在优于 O(N²) 的时间内找到该数组的互质子数组的数量？互质数组被定义为数组的连续子集，使得所有元素的 GCD 均为 1。

Answer 1

考虑在数组末尾添加一个元素。现在找到最右边的位置(如果有的话)，使得从该位置到您刚刚添加的元素的子数组互质。因为它在最右边，所以以添加的元素结尾的较短数组都不是互质的。因为它是互质的，所以从它的左边开始并以新元素结束的每个数组都是互质的。所以你已经计算出以新元素结尾的互质子数组的数量。如果你能有效地找到最右边的位置——比如在 O(log n) 而不是 O(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，那么我检查 7，发现 gcd(7, 13) = 1。因此我立即知道 GCD(5, 7, 13) = GCD(3, 5, 7, 13) = GCD(1, 3, 4, 7, 13) = 1。

列表 2、4、8、16。下一层是 2、8，根是 2。如果当前数字是 32，那么我检查 16，发现 gcd(16, 32) = 16 != 1所以然后我检查 8 并发现 GCD(8, 32) = 8 然后我检查 2 并发现 GCD(2, 32) = 2 所以在 GCD = 1 的扩展数组中没有间隔。