子数组 LCM/GCD/OR/AND 模板

题目	难度
CF1834E	rating 2300	LCM

题目	难度
2654. 使数组所有元素变成 1 的最少操作次数	困难	GCD
CF891A	rating 1500	GCD 同 2654
CF475D	rating 2000	GCD
CF1632D	rating 2000	GCD

题目	难度
898. 子数组按位或操作	中等	OR
2411. 按位或最大的最小子数组长度	中等	OR

题目	难度
1521. 找到最接近目标值的函数值	困难	AND 类似 898

原地去重

CF1834E

题目大意：

给定一个长度为 n 的数组 a。如果不可能找到数组的子段†使其所有元素的最小公倍数等于 x，则称为正整数 x。

你需要找到最小的好整数。

数组 A 的子段†是元素 al,al+1,...,ar 的集合，对于 1≤l≤r≤n。我们将这样的子段记为[l,r]。

import java.nio.charset.StandardCharsets;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

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

    // https://codeforces.com/contest/1834/submission/210047142
    private static String solve(int n, int[] a) {
        Set<Long> s = new HashSet<>();
        Set<Long> f = new HashSet<>();
        for (long ai : a) {
            Set<Long> g = new HashSet<>();
            for (Long fi : f) {
                long lcm = getLCM(fi, ai);
                if (lcm < INF) {
                    g.add(lcm);
                    s.add(lcm);
                }
            }
            g.add(ai);
            s.add(ai);
            f = g;
        }
        long x = 1;
        while (s.contains(x)) {
            x++;
        }
        return String.valueOf(x);
    }

    // <= n^2
    private static final long INF = (long) 1e10;

    private static long getLCM(long num1, long num2) {
        return num1 / getGCD(num1, num2) * num2;
    }

    private static long getGCD(long num1, long num2) {
        return num1 == 0 ? num2 : getGCD(num2 % num1, num1);
    }
}

CF891A

题目大意：

你有一个长度为 n 的数组 a，你可以执行一些操作。每个操作都是这样的:从 a 中选择两个相邻的元素，比如 x 和 y，并用 gcd(x, y)替换其中一个元素，其中 gcd 表示最大公约数。

使所有元素都等于 1 所需的最少操作次数是多少?

import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class CF891A {
    static int n;
    static int[] a;

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

    private static String solve() {
        int gcdAll = 0, cnt1 = 0;
        for (int x : a) {
            gcdAll = getGCD(gcdAll, x);
            if (x == 1) cnt1++;
        }
        if (gcdAll != 1) return "-1";
        if (cnt1 > 0) return String.valueOf(n - cnt1);

        int minLen = n;
        // gcd, 相同的 gcd 的最晚出现的位置
        List<int[]> g = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            g.add(new int[]{a[i], i});

            // 原地去重
            int k = 0;
            for (int[] p : g) {
                p[0] = getGCD(p[0], a[i]);
                if (g.get(k)[0] == p[0]) {
                    g.get(k)[1] = p[1]; // 合并相同值，下标取最小的
                } else {
                    k++;
                    g.set(k, p);
                }
            }
            g.subList(k + 1, g.size()).clear();

            if (g.get(0)[0] == 1) {
                // 这里本来是 i-g.get(0)[1]+1，把 +1 提出来合并到 return 中
                minLen = Math.min(minLen, i - g.get(0)[1]);
            }
        }
        return String.valueOf(n + (minLen - 1));
    }

    private static int getGCD(int num1, int num2) {
        return num1 == 0 ? num2 : getGCD(num2 % num1, num1);
    }
}

2411. 按位或最大的最小子数组长度

import java.util.ArrayList;
import java.util.List;

public class Solution2411 {
    public int[] smallestSubarrays(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        // 存 tuple: 按位或的值 + 对应子数组右端点的最小值
        List<int[]> ors = new ArrayList<>();
        for (int i = n - 1; i >= 0; i--) {
            int num = nums[i];
            ors.add(new int[]{0, i});
            int k = 0;
            for (int[] p : ors) {
                // 都或上 num
                p[0] |= num;
                // 去重/合并 取最小下标
                if (ors.get(k)[0] == p[0]) {
                    ors.get(k)[1] = p[1];
                } else {
                    k++;
                    ors.set(k, p);
                }
            }
            // del ors[k+1:]
            ors.subList(k + 1, ors.size()).clear();
            ans[i] = ors.get(0)[1] - i + 1;
        }
        return ans;
    }
}

898. 子数组按位或操作

import java.util.HashSet;
import java.util.Set;
import java.util.stream.Collectors;

public class Solution898 {
    public int subarrayBitwiseORs(int[] arr) {
        Set<Integer> ans = new HashSet<>();
        Set<Integer> ors = new HashSet<>();
        for (int x : arr) {
            ors = ors.stream().map(o -> o | x).collect(Collectors.toSet());
            ors.add(x);
            ans.addAll(ors);
        }
        return ans.size();
    }
}

1521. 找到最接近目标值的函数值

import java.util.HashSet;
import java.util.Set;
import java.util.stream.Collectors;

public class Solution1521 {
    public int closestToTarget(int[] arr, int target) {
        Set<Integer> ans = new HashSet<>();
        Set<Integer> ors = new HashSet<>();
        for (int x : arr) {
            ors = ors.stream().map(o -> o & x).collect(Collectors.toSet());
            ors.add(x);
            ans.addAll(ors);
        }
        return ans.stream().map(o -> Math.abs(o - target)).min(Integer::compareTo).orElseThrow();
    }
}

（全文完）