最大数不互为V

Question

给定N个整数的固定数组A，其中N<=100,000和数组的所有元素也小于或等于100,000。A中的数字不是单调增加的，也不是连续的，也不是很方便地组织起来的。

现在，我被给予多达100,000个形式的查询{ V，L，R}，在每个查询中，我需要在范围L，R中找到与i一起的最大数Ai，它与给定的值V不是对等的(即GCD(V，Ai)不等于1)。

如果这是不可能的，那么也说明在给定范围内的所有数字都与V是相互作用的。

一种基本的方法是从L和R之间的每个Ai迭代，然后用V值计算GCD，从而找到最大值。但是，如果查询的数量也可以达到100,000，那么是否有更好的方法来做到这一点呢？在这种情况下，每次检查每个数字的效率太低。

示例：

• 设N=6，阵列为1,2,3,4,5,4，V为2，距离L，R为2,5。
• 那么答案是4。

解释：

GCD(2,2)=2
GCD(2,3)=1
GCD(2,4)=2
GCD(2,5)=1

所以这里的最大值是4。

Answer 1

因为您有一个大数组，但只有一个V，所以通过分解V应该会更快。在此之后，您的互质测试就会简单地找到V的每个唯一因素的剩余模。

Answer 2

让我们说

V = p_1*...*p_n

其中p_i是一个素数(您可以将它限制为不同的素数)。现在的答案是

result = -1
for p_i:
    res = floor(R / p_i) * p_i
    if res >= L and res > result:
        result = res

因此，如果您能够快速地分解V，那么这将是相当有效的。

编辑我没有注意到数组不需要包含所有整数。在这种情况下，筛选它，即给定素数p_1，.，p_n创建一个“反向”筛(即范围[L, R]中素数的所有倍数)。然后你就可以和你的初始数组做一个筛子的交集。

EDIT2要生成所有倍数的集合，可以使用以下算法：

primes = [p_1, ..., p_n]
multiples = []
for p in primes:
    lower = floor(L / p)
    upper = floor(R / p)
    for i in [lower+1, upper]:
        multiples.append(i*p)

最重要的是，从数学上看，V与是相互作用的，在[L, R]范围内的每个数都不是multiples中的。现在你只需做：

solution = -1
for no in initial_array:
    if no in multiples:
        solution = max(solution, no)

注意，如果您将result作为一个集合来实现，那么if no in result:检查就是O(1)。

示例，比方说V = 6 = 2*3和initial_array = [7,11,12,17,21]，L=10和R=22。让我们从倍数开始。按照该算法，我们得到

multiples = [10, 12, 14, 16, 18, 20, 22, 12, 15, 18, 21]

前7是2的倍数(范围10，22)，最后4是3的倍数(范围10，22)。因为我们在处理集合(std::set?)然后就不会有重复(12和18)：

multiples = [10, 12, 14, 16, 18, 20, 22, 15, 21]

现在遍历initial_array并检查multiples中的值。我们得到的最大这样的数字是21。事实上，21与6并不是一回事。

Answer 3

Daniel的“在本质上线性时间内分解成互质” (算法杂志54:1，1-30 (2005))回答了一个类似的问题，并被用于识别Nadia的“新研究:没有必要对可分解密钥感到恐慌--只需注意你的Ps和Qs”的坏(重复因素) RSA模。问题是要在一组非常大的数字之间找出共同的因素，而不是一次一对。