arrays - 查找数组中是否存在两个互质数

Question

我试图找到一种算法，对于给定的整数数组 A = [a1, a2, ..., a_n] 如果有两个索引 i !== j 满足 gcd(ai, aj ) = 1(否则为假)。我试图将此算法的复杂性降至最低。

当然，显而易见的解决方案是对每一对 (ai, aj) 使用 Euclid 算法，但其悲观复杂度是 Euclid 算法复杂度的 n(n+1)/2 倍。

有没有办法在 O(n) 或 O(n*log(n)) 中做到这一点？

Answer 1

设 hasCoprimePair(S) 是一个过程，如果存在一对互素 S 则返回 True，否则返回 False，并让它有一个双参数变体 hasCoprimePair(S, T) 如果存在一对互素，则返回 True，一个S 中为整数，T 中为 1，否则为 False。

现在令 p 为质数。取一个集合 S(整数)并将其分成两个集合 T 和 U，以便 T 包含 S 中可被 p 整除的元素，而 U 包含其他元素(不可被 p 整除的元素)。因为 T 中的每个元素都可以被 p 整除，所以必然有 hasCoprimePair(T) = False。所以我们有

hasCoprimePair(S) = hasCoprimePair(T, U) or hasCoprimePair(U)

第一个子问题 (hasCoprimePair(T, U)) 可以在 |T|x|U| 中求解GCD-operations 和第二个子问题是递归的；这次您可以使用不同的 p 值再次拆分它。将 S 拆分为 T 和 U 集需要 O(n) 时间，因此与朴素算法相比，您节省了一些 GCD 操作，但渐近复杂度仍然是二次的。