首页算法

2709. 最大公约数遍历

难度困难

给你一个下标从 0 开始的整数数组 nums ，你可以在一些下标之间遍历。对于两个下标 i 和 j （ i != j ），当且仅当 gcd(nums[i], nums[j]) > 1 时，我们可以在两个下标之间通行，其中 gcd 是两个数的 最大公约数 。

你需要判断 nums 数组中 任意 两个满足 i < j 的下标 i 和 j ，是否存在若干次通行可以从 i 遍历到 j 。

如果任意满足条件的下标对都可以遍历，那么返回 true ，否则返回 false 。

示例 1：

输入：nums = [2,3,6]

输出：true

解释：这个例子中，总共有 3 个下标对：(0, 1) ，(0, 2) 和 (1, 2) 。

从下标 0 到下标 1 ，我们可以遍历 0 -> 2 -> 1 ，我们可以从下标 0 到 2 是因为 gcd (nums [0], nums [2]) = gcd (2, 6) = 2 > 1 ，从下标 2 到 1 是因为 gcd (nums [2], nums [1]) = gcd (6, 3) = 3 > 1 。

从下标 0 到下标 2 ，我们可以直接遍历，因为 gcd (nums [0], nums [2]) = gcd (2, 6) = 2 > 1 。同理，我们也可以从下标 1 到 2 因为 gcd (nums [1], nums [2]) = gcd (3, 6) = 3 > 1 。

示例 2：

输入：nums = [3,9,5]

输出：false

解释：我们没法从下标 0 到 2 ，所以返回 false 。

示例 3：

输入：nums = [4,3,12,8]

输出：true

解释：总共有 6 个下标对：(0, 1) ，(0, 2) ，(0, 3) ，(1, 2) ，(1, 3) 和 (2, 3) 。所有下标对之间都存在可行的遍历，所以返回 true 。

提示：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

# 分解质因数 + 并查集

若把每个数看作一个点，那么只有二者的 gcd>1gcd > 1 时，才会有边。

若直接每两个元素建图，那么时间复杂度为 n2n^2 级别。

我们可以用质因数作为中间点，让元素与其所有的质因数构成边。最后检查使用是否连通即可

img

由于每个数最多有 log nlog\,n 个质因数，即最终的时间复杂度为 O(n log(n⋅A))O(n\,log(n\cdot A))，其中 AA 为并查集的操作复杂度

class Solution {
    public boolean canTraverseAllPairs(int[] nums) {
        // 对每个元素求出不同质因数
        //  - 让该质因数作为中转点，将该元素与质因数联合起来
        int n = nums.length;
        init(200001);
        for (int j = 0; j < n; j++) {
            int num = nums[j];
            for (int i = 2; i * i <= num; i++) {
                if (num % i == 0) {
                    while (num % i == 0) {
                        num /= i;
                    }
                    // 此时 i 是 num 的一个质因数
                    // 合并 j 与 i 为一个连通分量
                    union(j, n + i);
                }
            }
            // 最后留下了一个质因数
            if (num > 1) {
                union(j, n + num);
            }
        }
        for (int i = 1; i < n; i++) {
            // 不为同一连通分量
            if (find(i) != find(i - 1)) {
                return false;
            }
        }
        return true;
    }
    int[] father;
    public void init(int n) {
        father = new int[n];
        for (int i = 1; i < n; i++) {
            father[i] = i;
        }
    }
    public void union(int i, int j) {
        int lAncestor = find(i);
        int rAncestor = find(j);
        // 左指向右
        father[lAncestor] = father[rAncestor];
    }
    public int find(int x) {
        if (x == father[x]) {
            return x;
        }
        return father[x] = find(father[x]);
    }
}


并查集 + 数学