LPF 与建图技巧：中转站

2023年12月17日大约 4 分钟

LPF 与建图技巧：中转站

题目	难度
952. 按公因数计算最大组件大小	困难
1998. 数组的最大公因数排序	困难
2709. 最大公约数遍历	困难
CF1775D	rating 1800

最小质因子 Least Prime Factor

The least prime factor of an integer n is the smallest prime number that divides the number.

整数 n 的最小素数因子是能整除该数的最小素数。

建图技巧：中转站

创建一个二部图，其左侧由 n 个顶点组成，顶点数为 ai。在右边，每个顶点对应一个质数，不大于左边的最大值。当且仅当 av 能被对应于顶点 u 的素数整除时，从左边部分的顶点 v 到右边部分的顶点 u 画一条边。

现在来看看如何快速地构造这样一个图。显然，数字 ai 最多有 logi 个不同的质因数。然后我们分解 av 并画出从顶点 v 到分解中每个素数的边。

O(n + U/logU) 个点
O(nlogU) 条边

952. 按公因数计算最大组件大小

import java.util.Arrays;

public class Solution952 {
    private static final int MAX_N = (int) (1e5 + 5);

    public int largestComponentSize(int[] nums) {
        int n = nums.length;

        int mx = Arrays.stream(nums).max().orElseThrow();
        // 埃氏筛 预处理 最小质因子
        int[] lpf = new int[mx + 1];
        for (int i = 2; i <= mx; i++) {
            if (lpf[i] == 0) {
                for (int j = i; j <= mx; j += i) {
                    if (lpf[j] == 0) {
                        lpf[j] = i;
                    }
                }
            }
        }

        DSU dsu = new DSU(n + mx + 1);
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            while (x > 1) {
                int p = lpf[x];
                for (x /= p; lpf[x] == p; x /= p) {
                }
                dsu.union(i, n + p);
            }
        }

        int[] cnt = new int[MAX_N];
        for (int i = 0; i < n; i++) {
            int fa = dsu.find(i);
            cnt[fa]++;
        }
        return Arrays.stream(cnt).max().orElseThrow();
    }

    private static class DSU {
        int[] fa;

        public DSU(int n) {
            fa = new int[n];
            for (int i = 0; i < n; i++) {
                fa[i] = i;
            }
        }

        int find(int x) {
            // 路径压缩
            if (x != fa[x]) {
                fa[x] = find(fa[x]);
            }
            return fa[x];
        }

        void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ) {
                return;
            }
            fa[rootQ] = rootP;
        }
    }
}

1998. 数组的最大公因数排序

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution1998 {
    public boolean gcdSort(int[] nums) {
        int n = nums.length;

        int mx = Arrays.stream(nums).max().orElseThrow();
        // 埃氏筛 预处理 最小质因子
        int[] lpf = new int[mx + 1];
        for (int i = 2; i <= mx; i++) {
            if (lpf[i] == 0) {
                for (int j = i; j <= mx; j += i) {
                    if (lpf[j] == 0) {
                        lpf[j] = i;
                    }
                }
            }
        }

        DSU dsu = new DSU(n + mx + 1);
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            while (x > 1) {
                int p = lpf[x];
                for (x /= p; lpf[x] == p; x /= p) {
                }
                dsu.union(n + p, i);
            }
        }

        // 分组排序
        Map<Integer, List<Integer>> groupsId = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int p = dsu.find(i) - n;
            groupsId.computeIfAbsent(p, key -> new ArrayList<>()).add(i);
        }
        for (List<Integer> ids : groupsId.values()) {
            List<Integer> vals = new ArrayList<>(ids.size());
            for (Integer id : ids) {
                vals.add(nums[id]);
            }
            vals.sort(null);
            int i = 0;
            for (Integer id : ids) {
                nums[id] = vals.get(i++);
            }
        }

        // 判断数组是否有序
        for (int i = 1; i < n; i++) {
            if (nums[i - 1] > nums[i]) return false;
        }
        return true;
    }

    private static class DSU {
        int[] fa;

        public DSU(int n) {
            fa = new int[n];
            for (int i = 0; i < n; i++) {
                fa[i] = i;
            }
        }

        int find(int x) {
            // 路径压缩
            if (x != fa[x]) {
                fa[x] = find(fa[x]);
            }
            return fa[x];
        }

        void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ) {
                return;
            }
            fa[rootQ] = rootP;
        }
    }
}

2709. 最大公约数遍历

import java.util.Arrays;

public class Solution2709 {
    public boolean canTraverseAllPairs(int[] nums) {
        int n = nums.length;

        int mx = Arrays.stream(nums).max().orElseThrow();
        // 埃氏筛 预处理 最小质因子
        int[] lpf = new int[mx + 1];
        for (int i = 2; i <= mx; i++) {
            if (lpf[i] == 0) {
                for (int j = i; j <= mx; j += i) {
                    if (lpf[j] == 0) {
                        lpf[j] = i;
                    }
                }
            }
        }

        // O(n + U/logU) 个点, O(nlogU) 条边
        DSU dsu = new DSU(n + mx + 1);
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            while (x > 1) {
                int p = lpf[x];
                for (x /= p; lpf[x] == p; x /= p) {
                }
                dsu.union(i, n + p);
            }
        }

        for (int i = 0; i < n; i++) {
            if (dsu.find(i) != dsu.find(0)) {
                return false;
            }
        }
        return true;
    }

    private static class DSU {
        int[] fa;

        public DSU(int n) {
            fa = new int[n];
            for (int i = 0; i < n; i++) {
                fa[i] = i;
            }
        }

        int find(int x) {
            // 路径压缩
            if (x != fa[x]) {
                fa[x] = find(fa[x]);
            }
            return fa[x];
        }

        void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ) {
                return;
            }
            fa[rootQ] = rootP;
        }
    }
}

CF1775D

import java.nio.charset.StandardCharsets;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.stream.Collectors;

public class CF1775D {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in, StandardCharsets.UTF_8);
        int n = scanner.nextInt();
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt();
        }
        int s = scanner.nextInt();
        int t = scanner.nextInt();
        System.out.println(solve(n, a, s, t));
    }

    private static String solve(int n, int[] a, int s, int t) {
        int mx = Arrays.stream(a).max().orElseThrow();

        // 埃氏筛 预处理 最小质因子
        int[] lpf = new int[mx + 1];
        for (int i = 2; i <= mx; i++) {
            if (lpf[i] == 0) {
                for (int j = i; j <= mx; j += i) {
                    if (lpf[j] == 0) {
                        lpf[j] = i;
                    }
                }
            }
        }

        Map<Integer, List<Integer>> adj = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            int x = a[i];
            while (x > 1) {
                int p = lpf[x];
                for (x /= p; lpf[x] == p; x /= p) {
                }
                adj.computeIfAbsent(i, key -> new ArrayList<>()).add(n + p);
                adj.computeIfAbsent(n + p, key -> new ArrayList<>()).add(i);
            }
        }

        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(s);
        Set<Integer> vis = new HashSet<>();
        vis.add(s);

        int[] pre = new int[n + mx + 5];
        Arrays.fill(pre, -1);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int x = queue.remove();
                if (x == t) {
                    List<Integer> ans = new ArrayList<>();
                    while (pre[x] != -1) {
                        if (x <= n) ans.add(x);
                        x = pre[x];
                    }
                    ans.add(s);
                    Collections.reverse(ans);
                    return ans.size() + System.lineSeparator()
                            + ans.stream().map(String::valueOf).collect(Collectors.joining(" "));
                }

                for (Integer y : adj.getOrDefault(x, new ArrayList<>())) {
                    if (!vis.contains(y)) {
                        vis.add(y);
                        // 记录转移来源（前继节点）
                        pre[y] = x;
                        queue.add(y);
                    }
                }
            }
        }
        return "-1";
    }
}

参考链接

Least prime factor of numbers till n

（全文完）