LPF 与建图技巧：中转站
大约 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";
}
}
参考链接
（全文完）