python3 解法, 执行用时: 576 ms, 内存消耗: 35.8 MB, 提交时间: 2023-05-28 10:58:57

@cache
def f(num):
    temp = []
    p, x = 2, num
    while p * p <= x:
        if x % p == 0:
            temp.append(p)
            x //= p
            while x % p == 0:
                x //= p
        p += 1
    if x > 1:
        temp.append(x)
    return tuple(temp)
    
    
class Solution:
    def canTraverseAllPairs(self, nums: List[int]) -> bool:
        if len(nums) == 1:
            return True

        nums = set(nums)
        if 1 in nums:
            return False

        nums = list(nums)
        n = len(nums)

        ps = set()
        for i, x in enumerate(nums):
            nums[i] = f(x)
            ps |= set(nums[i])

        p2i = dict()
        cnt = 0
        for p in ps:
            p2i[p] = n
            n += 1
            cnt += 1
        
        fa = list(range(n))
        
        def find(x):
            if fa[x] != x:
                fa[x] = find(fa[x])
            return fa[x]
        
        def union(x, y):
            x, y = find(x), find(y)
            fa[x] = y
        
        for i in range(len(nums)):
            c = 0
            for p in nums[i]:
                j = p2i[p]
                if find(i) != find(j):
                    union(i, j)
                    c += 1
            cnt -= max(c - 1, 0)
            if cnt == 1: return True
        return False

python3 解法, 执行用时: 380 ms, 内存消耗: 31.3 MB, 提交时间: 2023-05-28 10:58:26

# -*- coding: utf-8 -*-
from typing import List, Tuple
from collections import deque, Counter
from queue import PriorityQueue
import math
from functools import lru_cache
from sortedcontainers import SortedDict, SortedSet
import random
import copy
import sys
sys.setrecursionlimit(9999999)

MOD = 10**9 + 7


def get_prime(N):
    prime_vals = []
    flag = [True] * (N+1)
    for val in range(2, N+1):
        if flag[val]:
            prime_vals.append(val)

        for p_val in prime_vals:
            if val * p_val > N:
                break

            flag[val * p_val] = False

            if val % p_val == 0:
                break

    return prime_vals

primes = get_prime(1000)

def devide_prime(val):
    ans = []

    for i in primes:
        if i*i > val:
            break

        if val % i == 0:
            cnt = 0
            while val % i == 0:
                val //= i
                cnt += 1

            ans.append((i, cnt))

        if val == 1:
            break

    if val != 1:
        ans.append((val, 1))

    return ans

class Solution:
    def canTraverseAllPairs(self, nums: List[int]) -> bool:
        n = len(nums)
        if n == 1:
            return True

        for v in nums:
            if v == 1:
                return False

        nums = list(set(nums))

        e = set()
        P = set()
        for v in nums:
            ret = devide_prime(v)
            for p, cnt in ret:
                P.add(p)

            k = len(ret)
            for i in range(k):
                for j in range(i+1, k):
                    a, b = ret[i][0], ret[j][0]
                    e.add((a, b))

        p = {}
        for x in P:
            p[x] = x

        def rt(x):
            if p[x] != x:
                p[x] = rt(p[x])
            return p[x]

        def merge(a, b):
            aa, bb = rt(a), rt(b)
            if aa != bb:
                p[aa] = bb

        for a, b in e:
            merge(a, b)

        rt_set = set()
        for x in P:
            rt_set.add(rt(x))
            if len(rt_set) >= 2:
                return False

        return True

cpp 解法, 执行用时: 276 ms, 内存消耗: 91.9 MB, 提交时间: 2023-05-28 10:57:36

/**
 * 把 nums 中的每个位置看成一个点，把所有质数也都看成一个点。
 * 如果 nums[i] 被质数 p 整除，那么从位置点 i 向质数点 p 连一条边。
 * 因为每个数至多只能被 log 个质数整除，因此连边的总数是 O(nlogA) 的。
 * 这样，问题就变为：检查所有位置点是否处于同一连通块内。用并查集解决即可。
 **/
#define MAXX ((int) 1e5)
bool inited = false;
vector<int> fac[MAXX + 10];

// 全局预处理每个数的质因数
void init() {
    if (inited) return;
    inited = true;

    for (int i = 2; i <= MAXX; i++) if (fac[i].empty()) for (int j = i; j <= MAXX; j += i) fac[j].push_back(i);
}

class Solution {
public:
    bool canTraverseAllPairs(vector<int>& nums) {
        init();

        int n = nums.size();
        int mx = 0;
        for (int x : nums) mx = max(mx, x);

        // 初始化并查集
        int root[n + mx + 1];
        for (int i = 0; i <= n + mx; i++) root[i] = i;

        // 查询并查集的根
        function<int(int)> findroot = [&](int x) {
            if (root[x] != x) root[x] = findroot(root[x]);
            return root[x];
        };

        // 对每个 nums[i]，向它们的质因数连边
        for (int i = 0; i < n; i++) for (int p : fac[nums[i]]) {
            int x = findroot(i), y = findroot(n + p);
            if (x == y) continue;
            root[x] = y;
        }

        // 检查是否所有位置点都在同一连通块内
        unordered_set<int> st;
        for (int i = 0; i < n; i++) st.insert(findroot(i));
        return st.size() == 1;
    }
};