以下是 LeetCode 3953. 互质元素的最大得分 的完整 Java 实现javaimport java.util.*;class Solution {private static final int N 100001;// primeFactors[i] 存储 i 的所有不同质因数SuppressWarnings(unchecked)private static final ListInteger[] primeFactors new ArrayList[N];// 预处理每个数的不同质因数筛法static {for (int i 0; i N; i) {primeFactors[i] new ArrayList();}for (int i 2; i N; i) {if (primeFactors[i].isEmpty()) { // i 是质数for (int j i; j N; j i) {primeFactors[j].add(i);}}}}public int maxScore(int[] nums, int maxVal) {// cnt[d]原数组中能被 d 整除的数的个数d 是质因数子集的乘积int[] cnt new int[N];// present[x]x 在原数组中出现的次数int[] present new int[N];for (int x : nums) {if (x N) {present[x];}ListInteger pf primeFactors[x];int sz pf.size();// 枚举所有非空子集统计各乘积的倍数个数for (int mask 1; mask (1 sz); mask) {int prod 1;for (int i 0; i sz; i) {if ((mask i 1) 1) {prod * pf.get(i);}}if (prod N) {cnt[prod];}}}int res Integer.MIN_VALUE;// 1. 处理 selectedValue 1 的情况if (maxVal 1) {if (present[1] 0) {// 1 在原数组中无需修改且 1 与任何数互质res Math.max(res, 1);} else {// 需要把一个元素修改为 1代价为 1res Math.max(res, 0); // 1 - 1 0}}// 2. 枚举 selectedValue 从 2 到 maxValfor (int v 2; v maxVal; v) {int notCoprime getNotCoprimeCount(v, cnt);if (present[v] 0) {// v 在原数组中v 与自身不互质v 1需减去自身这一次int cost notCoprime - 1;res Math.max(res, v - cost);} else {// v 不在原数组中至少要花费 1 次修改来创建vint cost notCoprime 0 ? 1 : notCoprime;res Math.max(res, v - cost);}}// 3. 处理原数组中大于 maxVal 的元素作为 selectedValue不修改它boolean[] visited new boolean[N];for (int x : nums) {if (x maxVal || x N || visited[x]) continue;visited[x] true;if (x 1) continue; // 1 已处理int notCoprime getNotCoprimeCount(x, cnt);int cost notCoprime - 1; // x 与自身不互质减去自身res Math.max(res, x - cost);}return res;}// 使用容斥原理计算原数组中与 x 不互质的元素个数private int getNotCoprimeCount(int x, int[] cnt) {ListInteger pf primeFactors[x];int sz pf.size();int total 0;for (int mask 1; mask (1 sz); mask) {int prod 1;int bits 0;for (int i 0; i sz; i) {if ((mask i 1) 1) {prod * pf.get(i);bits;}}if (prod N) {// 容斥奇数个质因数相加偶数个质因数相减if ((bits 1) 1) {total cnt[prod];} else {total - cnt[prod];}}}return total;}}---核心思路步骤 说明质因数预处理 用筛法在 static 块中预处理 [1, 10^5] 每个数的不同质因数倍数统计 对数组中每个数枚举其质因数的所有非空子集统计各乘积的倍数个数到 cnt[]容斥原理 对候选值 v通过容斥计算数组中与 v 不互质的元素个数三种候选 分别枚举 selectedValue 为 1、 [2, maxVal] 中的值、以及原数组中大于 maxVal 且未修改的元素复杂度- 时间复杂度O(N × 2^ω)其中 ω 是数的不同质因数个数≤ 6因为 2×3×5×7×11×13 30030 10^5所以 2^ω ≤ 64- 空间复杂度O(N) Kimi LeetCode 3953. 互质元素的最大得分 Java实现
以下是 LeetCode 3953. 互质元素的最大得分 的完整 Java 实现javaimport java.util.*;class Solution {private static final int N 100001;// primeFactors[i] 存储 i 的所有不同质因数SuppressWarnings(unchecked)private static final ListInteger[] primeFactors new ArrayList[N];// 预处理每个数的不同质因数筛法static {for (int i 0; i N; i) {primeFactors[i] new ArrayList();}for (int i 2; i N; i) {if (primeFactors[i].isEmpty()) { // i 是质数for (int j i; j N; j i) {primeFactors[j].add(i);}}}}public int maxScore(int[] nums, int maxVal) {// cnt[d]原数组中能被 d 整除的数的个数d 是质因数子集的乘积int[] cnt new int[N];// present[x]x 在原数组中出现的次数int[] present new int[N];for (int x : nums) {if (x N) {present[x];}ListInteger pf primeFactors[x];int sz pf.size();// 枚举所有非空子集统计各乘积的倍数个数for (int mask 1; mask (1 sz); mask) {int prod 1;for (int i 0; i sz; i) {if ((mask i 1) 1) {prod * pf.get(i);}}if (prod N) {cnt[prod];}}}int res Integer.MIN_VALUE;// 1. 处理 selectedValue 1 的情况if (maxVal 1) {if (present[1] 0) {// 1 在原数组中无需修改且 1 与任何数互质res Math.max(res, 1);} else {// 需要把一个元素修改为 1代价为 1res Math.max(res, 0); // 1 - 1 0}}// 2. 枚举 selectedValue 从 2 到 maxValfor (int v 2; v maxVal; v) {int notCoprime getNotCoprimeCount(v, cnt);if (present[v] 0) {// v 在原数组中v 与自身不互质v 1需减去自身这一次int cost notCoprime - 1;res Math.max(res, v - cost);} else {// v 不在原数组中至少要花费 1 次修改来创建vint cost notCoprime 0 ? 1 : notCoprime;res Math.max(res, v - cost);}}// 3. 处理原数组中大于 maxVal 的元素作为 selectedValue不修改它boolean[] visited new boolean[N];for (int x : nums) {if (x maxVal || x N || visited[x]) continue;visited[x] true;if (x 1) continue; // 1 已处理int notCoprime getNotCoprimeCount(x, cnt);int cost notCoprime - 1; // x 与自身不互质减去自身res Math.max(res, x - cost);}return res;}// 使用容斥原理计算原数组中与 x 不互质的元素个数private int getNotCoprimeCount(int x, int[] cnt) {ListInteger pf primeFactors[x];int sz pf.size();int total 0;for (int mask 1; mask (1 sz); mask) {int prod 1;int bits 0;for (int i 0; i sz; i) {if ((mask i 1) 1) {prod * pf.get(i);bits;}}if (prod N) {// 容斥奇数个质因数相加偶数个质因数相减if ((bits 1) 1) {total cnt[prod];} else {total - cnt[prod];}}}return total;}}---核心思路步骤 说明质因数预处理 用筛法在 static 块中预处理 [1, 10^5] 每个数的不同质因数倍数统计 对数组中每个数枚举其质因数的所有非空子集统计各乘积的倍数个数到 cnt[]容斥原理 对候选值 v通过容斥计算数组中与 v 不互质的元素个数三种候选 分别枚举 selectedValue 为 1、 [2, maxVal] 中的值、以及原数组中大于 maxVal 且未修改的元素复杂度- 时间复杂度O(N × 2^ω)其中 ω 是数的不同质因数个数≤ 6因为 2×3×5×7×11×13 30030 10^5所以 2^ω ≤ 64- 空间复杂度O(N)