6.数学（0x3f：从周赛中学算法 2022下）

来自0x3f【从周赛中学算法 - 2022 年周赛题目总结（下篇）】：https://leetcode.cn/circle/discuss/WR1MJP/
主要考察的是数论（质数、GCD、LCM、逆元等）和组合数学。
注：占比很少，不足 10%。

其他23：

灵神-从周赛中学算法（数学）

2507. 使用质因数之和替换后可以取到的最小值

难度中等11

给你一个正整数 n 。

请你将 n 的值替换为 n 的 质因数 之和，重复这一过程。

• 注意，如果 n 能够被某个质因数多次整除，则在求和时，应当包含这个质因数同样次数。

返回 n 可以取到的最小值。

示例 1：

输入：n = 15
输出：5
解释：最开始，n = 15 。
15 = 3 * 5 ，所以 n 替换为 3 + 5 = 8 。
8 = 2 * 2 * 2 ，所以 n 替换为 2 + 2 + 2 = 6 。
6 = 2 * 3 ，所以 n 替换为 2 + 3 = 5 。
5 是 n 可以取到的最小值。
1
2
3
4
5
6
7

示例 2：

输入：n = 3
输出：3
解释：最开始，n = 3 。
3 是 n 可以取到的最小值。
1
2
3
4

提示：

• 2 <= n <= 105

题解：https://leetcode.cn/problems/smallest-value-after-replacing-with-sum-of-prime-factors/solution/bao-li-by-endlesscheng-xh0b/

不断循环，计算n的质因数之和s，如果 s==n 说明无法再继续减小了，返回n，否则更新n为s，继续循环。

• 为什么**i从小到大枚举**一定能够枚举所有质因数？ 唯一分解定理

举例：i=4时，此时前面i=2已经整除过n了，能够保证当i能整除n时，这个i一定是质数

java：

class Solution {
    /*
    1. n怎么变？
    	a + n/a
    	2 + n/2
    2. n是不会变大的
     ==> 不断循环，直到质因数之和 等于n 为止
    */
    public int smallestValue(int n) {
        while(true){
            int x = n;
            int sum = 0;
            int i = 2;
            //i从小到大枚举，如果大的i能整除n，小的i肯定能整除n，这是矛盾的
            while(i * i <= x){
                while(x % i == 0){
                    sum += i;
                    x /= i;
                }
                i++;
            }
            if(x > 1) sum += x; // x还有剩余，本身也是质数
            if(sum == n) return n;
            n = sum;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

Go：

func smallestValue(n int) int {
    res := -1
    for res == -1 {
        x := n
        sum := 0
        i := 2
        for i * i <= n {
            for x % i == 0 {
                sum += i
                x /= i
            }
            i++
        }
        if x > 1 {
            sum += x
        }
        if sum == n {
            res = n
        }
        n = sum
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2470. 最小公倍数为 K 的子数组数目

难度中等25

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的 子数组 中满足 元素最小公倍数为 k 的子数组数目。

子数组 是数组中一个连续非空的元素序列。

数组的最小公倍数 是可被所有数组元素整除的最小正整数。

示例 1 ：

输入：nums = [3,6,2,7,1], k = 6
输出：4
解释：以 6 为最小公倍数的子数组是：
- [3,6,2,7,1]
- [3,6,2,7,1]
- [3,6,2,7,1]
- [3,6,2,7,1]
1
2
3
4
5
6
7

示例 2 ：

输入：nums = [3], k = 2
输出：0
解释：不存在以 2 为最小公倍数的子数组。
1
2
3

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i], k <= 1000

方法一：暴力

• 为什么枚举时minlcm要初始化为1？因为1和任何数x的最小公倍数都是x

class Solution {
    /*
    枚举+递推+剪枝:
        nums[i,j]的最小公倍数=nums[i,j-1]的最小公倍数*nums[j]/gcd(nums[i,j-1]的最小公倍,nums[j])
        即把nums[i,j-1]的最小公倍数看做一个整体
        f[i,j]=f[i,j-1]*nums[j]/gcd(f[i,j-1],nums[j])
     */
    public int subarrayLCM(int[] nums, int k) {
        int n = nums.length;
        int res = 0;
        for(int i = 0; i < n; i++){
            // 枚举起点
            int min = 1; // min为nums[i,j]的最小公倍数
            //为什么枚举时 min 要初始化为1？因为1和任何数x的最小公倍数都是x
            for(int j = i; j < n; j++){
                min = lcm(min, nums[j]); // 计算最小公倍数
                if(min > k) 
                    break; // 剪枝：前面超过了k，最小公倍数不可能为k
                if(min == k) res++;    
            }
        }
        return res;
    }

    public int gcd(int x, int y){
        return y == 0 ? x : gcd(y,x%y);
    }

    public int lcm(int x, int y){
        return x*y / gcd(x, y);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

go语言：

func subarrayLCM(nums []int, k int) int {
    n := len(nums)
    res := 0
    for i := 0; i < n; i++ {
        min := 1
        for j := i; j < n; j++ {
            min = lcm(min, nums[j])
            if min > k { break}
            if min == k {
                res++
            }
        }
    }
    return res
}

func gcd(x, y int) int {
    for x != 0 {
        x, y = y%x, x
    }
    return y
}

func lcm(x, y int) int {
    return x*y / gcd(x, y)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

2447. 最大公因数等于 K 的子数组数目

难度中等25

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的子数组中元素的最大公因数等于 k 的子数组数目。

子数组 是数组中一个连续的非空序列。

数组的最大公因数 是能整除数组中所有元素的最大整数。

示例 1：

输入：nums = [9,3,1,2,6,3], k = 3
输出：4
解释：nums 的子数组中，以 3 作为最大公因数的子数组如下：
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
1
2
3
4
5
6
7

示例 2：

输入：nums = [4], k = 7
输出：0
解释：不存在以 7 作为最大公因数的子数组。
1
2
3

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i], k <= 109

方法一：暴力

// 无优化暴力
class Solution {
    public int subarrayGCD(int[] nums, int k) {
        int n = nums.length;
        int res = 0;
        // 从i开始往后拓展子数组
        for(int i = 0; i < n; i++){
            int g = 0;
            for(int j = i; j < n; j++){
                g = gcd(g, nums[j]);
                if(g == k) res++;
            }
        }
        return res;
    }

    public int gcd(int x, int y){
        return y == 0 ? x : gcd(y, x%y);
    }
}
// 优化版本
class Solution {
    public int subarrayGCD(int[] nums, int k) {
        int n = nums.length;
        int res = 0;
        // 从i开始往后拓展子数组
        for(int i = 0; i < n; i++){
            // 如果nums[i]不是k的倍数，肯定没有k这个因数
            if(nums[i] % k != 0) continue;
            int g = 0;
            for(int j = i; j < n; j++){
                g = gcd(g, nums[j]);
                if(g == k) res++;
            }
        }
        return res;
    }

    public int gcd(int x, int y){
        return y == 0 ? x : gcd(y, x%y);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

2344. 使数组可以被整除的最少删除次数

难度困难14

给你两个正整数数组 nums 和 numsDivide 。你可以从 nums 中删除任意数目的元素。

请你返回使 nums 中 最小 元素可以整除 numsDivide 中所有元素的 最少 删除次数。如果无法得到这样的元素，返回 -1 。

如果 y % x == 0 ，那么我们说整数 x 整除 y 。

示例 1：

输入：nums = [2,3,2,4,3], numsDivide = [9,6,9,3,15]
输出：2
解释：
[2,3,2,4,3] 中最小元素是 2 ，它无法整除 numsDivide 中所有元素。
我们从 nums 中删除 2 个大小为 2 的元素，得到 nums = [3,4,3] 。
[3,4,3] 中最小元素为 3 ，它可以整除 numsDivide 中所有元素。
可以证明 2 是最少删除次数。
1
2
3
4
5
6
7

示例 2：

输入：nums = [4,3,6], numsDivide = [8,2,6,10]
输出：-1
解释：
我们想 nums 中的最小元素可以整除 numsDivide 中的所有元素。
没有任何办法可以达到这一目的。
1
2
3
4
5

提示：

• 1 <= nums.length, numsDivide.length <= 105

• 1 <= nums[i], numsDivide[i] <= 109

• 居然自己想出来了，说明前面学的都是有用的！加油

class Solution {
    //  a 整除 b ==> b%a == 0 ==> a是b的公因数
    public int minOperations(int[] nums, int[] numsDivide) {
        // 计算target 数组的最大公因数 GCD
        int g = 0;
        for(int i = 0; i < numsDivide.length; i++){
            g = gcd(g, numsDivide[i]);
        }
        //从小到大枚举nums，找到第一个与g gcd值=nums[i]的数
        Arrays.sort(nums);
        int i = 0;
        while(i < nums.length){
            int cur = gcd(nums[i], g);
            // 最大公因数是nums[i]，说明nums[i]和numsDivide的整体的最大公因数是nums[i]，能被整除
            if(cur == nums[i]) break;
            i++;
        }
        if(i == nums.length) return -1;
        return i;
    }

    public int gcd(int x, int y){
        return y == 0 ? x : gcd(y, x%y);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

2453. 摧毁一系列目标

难度中等9

给你一个下标从 0 开始的数组 nums ，它包含若干正整数，表示数轴上你需要摧毁的目标所在的位置。同时给你一个整数 space 。

你有一台机器可以摧毁目标。给机器 输入 nums[i] ，这台机器会摧毁所有位置在 nums[i] + c * space 的目标，其中 c 是任意非负整数。你想摧毁 nums 中 尽可能多 的目标。

请你返回在摧毁数目最多的前提下，nums[i] 的 最小值 。

示例 1：

输入：nums = [3,7,8,1,1,5], space = 2
输出：1
解释：如果我们输入 nums[3] ，我们可以摧毁位于 1,3,5,7,9,... 这些位置的目标。
这种情况下， 我们总共可以摧毁 5 个目标（除了 nums[2]）。
没有办法摧毁多于 5 个目标，所以我们返回 nums[3] 。
1
2
3
4
5

示例 2：

输入：nums = [1,3,5,2,4,6], space = 2
输出：1
解释：输入 nums[0] 或者 nums[3] 都会摧毁 3 个目标。
没有办法摧毁多于 3 个目标。
由于 nums[0] 是最小的可以摧毁 3 个目标的整数，所以我们返回 1 。
1
2
3
4
5

示例 3：

输入：nums = [6,2,5], space = 100
输出：2
解释：无论我们输入哪个数字，都只能摧毁 1 个目标。输入的最小整数是 nums[1] 。
1
2
3

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• 1 <= space <= 109

class Solution {
    /*
 预处理+枚举:
1.枚举每个数字，计算出对space取余后的结果，这个结果范围在[0,space-1]
2.只要取余后结果一致，那么必定存在一个最小值使得所有同余数的点被摧毁
3.只要找出出现次数最多的几个余数，然后再再这些余数之中找出对应的最小的nums[i]就是答案
时间复杂度:O(N) 空间复杂度:O(N)
    */
    
    // 同余：如果(x-y) mod m = 0，那么称x与y对模m同余
    public int destroyTargets(int[] nums, int space) {
        // 1,3,5,7 % s(s=2)  => 1 ==> 同余分组
        Map<Integer, Integer> map = new HashMap<>(); // 统计每个余数出现次数（同余分组）
        for(int i = 0; i < nums.length; i++){
            map.put((nums[i] % space + space) % space, map.getOrDefault((nums[i] % space + space) % space, 0) + 1);
        }
        int res = 0, max = 0;
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i++){
            int reminder = (nums[i] % space) % space; // 得到当前数的余数
            if(map.getOrDefault(reminder, 0) > max){
                res = nums[i];
                max = map.get(reminder);
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

2514. 统计同位异构字符串数目

难度困难12

给你一个字符串 s ，它包含一个或者多个单词。单词之间用单个空格 ' ' 隔开。

如果字符串 t 中第 i 个单词是 s 中第 i 个单词的一个 排列 ，那么我们称字符串 t 是字符串 s 的同位异构字符串。

• 比方说，"acb dfe" 是 "abc def" 的同位异构字符串，但是 "def cab" 和 "adc bef" 不是。

请你返回 s 的同位异构字符串的数目，由于答案可能很大，请你将它对 109 + 7 取余 后返回。

示例 1：

输入：s = "too hot"
输出：18
解释：输入字符串的一些同位异构字符串为 "too hot" ，"oot hot" ，"oto toh" ，"too toh" 以及 "too oht" 。
1
2
3

示例 2：

输入：s = "aa"
输出：1
解释：输入字符串只有一个同位异构字符串。
1
2
3

提示：

• 1 <= s.length <= 105
• s 只包含小写英文字母和空格 ' ' 。
• 相邻单词之间由单个空格隔开。

题解：

视频讲解：https://www.bilibili.com/video/BV1Dd4y1h72z/

首先要明确，(a/b)%c=(a%c)/(b%c)是不成立的，除法取模并不像加减乘那样可以直接分离，而要通过逆元计算

• 除法取模记住 费马小定理 公式：a / b(mod p) = a * pow(b,p-2) mod p

class Solution {
    private static final int MOD = (int) 1e9 + 7;
    // 首先，每个单词自己是互相独立的，因此分别计算每个单词的同位异构字符串的数目，再用乘法原理相乘
    // 对于一个长为 n 的单词，其全排列的个数为 n!
    // 但由于相同的字母不做区分，所以如果有x个字母a，还需要除以这些a的全排列的个数，即x!
    // too => 3!/2! = 3
    // hot => 3!/1! = 6
    // 问题在于[3!/2!]怎么搞定除法? 费马小定理
    // 代码实现时，分子分母可以分别计算，最后再用 费马小定理 相除
    public int countAnagrams(String s) {
        char[] c = s.toCharArray();
        long ans = 1L, mul = 1L;
        int[] cnt = new int[26];
        for(int i = 0, j = 0; i < c.length; i++){
            if(c[i] == ' '){
                Arrays.fill(cnt, 0);
                j = 0;
            }else{
                ans = ans * ++j % MOD;
                mul = mul * ++cnt[c[i] - 'a'] % MOD;
            }
        }
        return (int)(ans * pow(mul, MOD - 2) % MOD);
    }

    public long pow(long x, int n) {
        long res = 1L;
        for(; n > 0; n /= 2){
            if(n % 2 > 0) res = res * x % MOD;
            x = x * x % MOD;
        }
        return res;
    }
}
// 费马小定理：a, p 互素, 且 p 为素数 a^(p-1) mod p = 1 
//  记住公式：a / b(mod p) = a*pow(b,p-2)mod p
// 
// 推导: (ans / mul) mod p = (ans / mul * 1) mod p 
//                         = (ans / mul * mul ^ (p - 1)) mod p 
//                         = (ans * mul ^ (p - 2)) mod p
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

---

来源：https://leetcode.cn/problems/count-anagrams/solution/c-by-code_learner-vwxz/

补充一下：

对于一个n长度的字符串，排列数计算。假设有n1个‘a’, n2个 ‘b’, n2个 ‘c’,那么生成的字符串的数量最终为：

(n1+n2+n3)!
-------------    【除号】     公式(1)  
n1! * n2! *n3!
1
2
3

显然java代码中，A[i]计算的就是 i!,那么g[i]计算的是什么呢，为什么要多一个g[i]计算？ 因为我们计算的是形如

  b
----    【除号】
  a
1
2
3

的形式，当a，b都比较大的时候，这时，你再来上一个%MOD，计算上有问题【具体为什么，我也不会，反正就是不能这么直接计算】。应该计算 b*a(-1)【说明：b乘以a的-1次方】,这样计算再去%MOD才对【感觉意思就是%MOD对于除法不能直接用，嗯，先这样记着】。a(-1)%MOD【a的-1次方再对MOD取余】该怎么计算呢，很明显a(-1)，会出现小数的。所以这里用到了费马小定理。

有两个数字，a（不是p的倍数），p（质数）。a的p-1方 和 1 对p同余
 
比如 a是3，p是5 ，那么a的p-1方是81，81%5 = 1。
再比如 a是4，p是3 ，那么a的p-1方是16，16%3 = 1。

因此，a^(-1)%MOD  【把它看作1】=  a^(p-2)%MOD 【a^(p-2)是a的p-2次方】
1
2
3
4
5
6

总结一下：排列组合公式(1) 的计算，关键在于处理分母， a^(-1)%MOD = a^(p-2)%MOD ， 即得会转化为pow(a, p)函数计算。剩下的就是洒洒水啦

class Solution {
    private static final int MOD = (int) 1e9 + 7;
    
    public int countAnagrams(String s) {
        long a = 1, b = 1;
        int[] cnt = new int[26];
        for (String word : s.split(" ")) {
            int n = word.length();
            char[] chars = word.toCharArray();
            Arrays.fill(cnt, 0);
            for (int i = 0; i < n; i++) {
                a = a * (i + 1) % MOD;
                cnt[chars[i] - 'a']++;
                b = b * cnt[chars[i] - 'a'] % MOD;
            }
        }
        return (int) (a * qpow(b, MOD - 2) % MOD);
    }

    public long qpow(long x, int n) {
        long res = 1L;
        for(; n > 0; n /= 2){
            if(n % 2 > 0) res = res * x % MOD;
            x = x * x % MOD;
        }
        return res;
    }
}
// too => 3!/2! = 3 ； hot => 3!/1! = 6
// 如何计算单词的排列？
// 例如too： a = 1; b = 1
// 	第一次loop： a = a * 1 = 1 ; b = b * 1 = 1
//  第二次loop： a = a * 2 = 2 ; b = b * 1 = 1
//  第三次loop： a = a * 3 = 6 ; b = b * 2 = 2
// 最后too这个单词的排列  6/2 
// 因为可能很大，要取余，而除法没有(a/b)%c=(a%c)/(b%c)
// 所以最后用费马小定理： a / b % MOD = a * (b^(MOD-2)) % MOD 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

---

2513. 最小化两个数组中的最大值

难度中等26

给你两个数组 arr1 和 arr2 ，它们一开始都是空的。你需要往它们中添加正整数，使它们满足以下条件：

• arr1 包含 uniqueCnt1 个 互不相同 的正整数，每个整数都 不能 被 divisor1 整除 。
• arr2 包含 uniqueCnt2 个 互不相同 的正整数，每个整数都 不能 被 divisor2 整除 。
• arr1 和 arr2 中的元素 互不相同 。

给你 divisor1 ，divisor2 ，uniqueCnt1 和 uniqueCnt2 ，请你返回两个数组中 最大元素 的 最小值 。

示例 1：

输入：divisor1 = 2, divisor2 = 7, uniqueCnt1 = 1, uniqueCnt2 = 3
输出：4
解释：
我们可以把前 4 个自然数划分到 arr1 和 arr2 中。
arr1 = [1] 和 arr2 = [2,3,4] 。
可以看出两个数组都满足条件。
最大值是 4 ，所以返回 4 。
1
2
3
4
5
6
7

示例 2：

输入：divisor1 = 3, divisor2 = 5, uniqueCnt1 = 2, uniqueCnt2 = 1
输出：3
解释：
arr1 = [1,2] 和 arr2 = [3] 满足所有条件。
最大值是 3 ，所以返回 3 。
1
2
3
4
5

示例 3：

输入：divisor1 = 2, divisor2 = 4, uniqueCnt1 = 8, uniqueCnt2 = 2
输出：15
解释：
最终数组为 arr1 = [1,3,5,7,9,11,13,15] 和 arr2 = [2,6] 。
上述方案是满足所有条件的最优解。
1
2
3
4
5

提示：

• 2 <= divisor1, divisor2 <= 105
• 1 <= uniqueCnt1, uniqueCnt2 < 109
• 2 <= uniqueCnt1 + uniqueCnt2 <= 109

class Solution {
    // 一看到「最大值的最小值」就想到二分答案。
    // 推荐用 4 和 6 尝试
    // d1 = 4, d2 = 6
    // arr1  1 2 3   5 6 7   9 10 11   13
    // arr2  1 2 3 4 5   7 8 9 10 11   13
    // ==> 找到一些规律
    // arr1 独占 6 的倍数，但又不是 4 的倍数(或者说不能是LCM(6, 4) = 12 的倍数)
    // arr2 独占 4 的倍数，但又不是 6 的倍数(或者说不能是LCM(6, 4) = 12 的倍数)
    // arr1 2 独享 既不是 4 的倍数， 也不是 6 的倍数
    //        = 所有数的个数 - (4 的倍数 + 6 的倍数 - 12 的倍数)
    //  最大元素 的 最小值  : 二分答案（答案越大，能选的数越多，越能组成满足要求的arr1和arr2）
    // 最坏情况下 divisor1, divisor2 = 2， 只能选奇数
    public int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
        // divisor1 和 divisor2 的最大公倍数，它可能会造成 int 溢出，所以需要使用 long。
        long g = lcm(divisor1, divisor2);
        long left = 0;
        long right =2 * ((long)uniqueCnt1 + (long)uniqueCnt2) - 1;
        while(left <= right){
            long mid = (left + right) / 2;
            if(check(mid, g, divisor1, divisor2, uniqueCnt1, uniqueCnt2)) right = mid - 1;
            else left = mid + 1;
        }
        return (int)left;
    }

    public boolean check(long x, long g, int d1, int d2, int u1, int u2){
        long cnt1 = x - x / d1; // 不能被 divisor1 整除的数
        long cnt2 = x - x / d2; // 不能被 divisor2 整除的数
        long cnt3 = x - x / g;  // 不能被 最大公倍数 整除的数
        return cnt1 >= u1 &&
               cnt2 >= u2 &&
               cnt3 >= (u1 + u2); // 能选数的个数大于需要的数u1 和 u2 之和
    }       

    public int gcd(int x, int y){
        return y == 0 ? x : gcd(y, x%y);
    }

    public long lcm(int x, int y){
        return (long)x * y / gcd(x, y);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

2338. 统计理想数组的数目

难度困难49

给你两个整数 n 和 maxValue ，用于描述一个 理想数组 。

对于下标从 0 开始、长度为 n 的整数数组 arr ，如果满足以下条件，则认为该数组是一个 理想数组 ：

• 每个 arr[i] 都是从 1 到 maxValue 范围内的一个值，其中 0 <= i < n 。
• 每个 arr[i] 都可以被 arr[i - 1] 整除，其中 0 < i < n 。

返回长度为 n 的 不同 理想数组的数目。由于答案可能很大，返回对 109 + 7 取余的结果。

示例 1：

输入：n = 2, maxValue = 5
输出：10
解释：存在以下理想数组：
- 以 1 开头的数组（5 个）：[1,1]、[1,2]、[1,3]、[1,4]、[1,5]
- 以 2 开头的数组（2 个）：[2,2]、[2,4]
- 以 3 开头的数组（1 个）：[3,3]
- 以 4 开头的数组（1 个）：[4,4]
- 以 5 开头的数组（1 个）：[5,5]
共计 5 + 2 + 1 + 1 + 1 = 10 个不同理想数组。
1
2
3
4
5
6
7
8
9

示例 2：

输入：n = 5, maxValue = 3
输出：11
解释：存在以下理想数组：
- 以 1 开头的数组（9 个）：
   - 不含其他不同值（1 个）：[1,1,1,1,1] 
   - 含一个不同值 2（4 个）：[1,1,1,1,2], [1,1,1,2,2], [1,1,2,2,2], [1,2,2,2,2]
   - 含一个不同值 3（4 个）：[1,1,1,1,3], [1,1,1,3,3], [1,1,3,3,3], [1,3,3,3,3]
- 以 2 开头的数组（1 个）：[2,2,2,2,2]
- 以 3 开头的数组（1 个）：[3,3,3,3,3]
共计 9 + 1 + 1 = 11 个不同理想数组。
1
2
3
4
5
6
7
8
9
10

提示：

• 2 <= n <= 104
• 1 <= maxValue <= 104

class Solution:
     def idealArrays(self, n: int, maxValue: int) -> int:
        mod = 10 ** 9 + 7
        max_k = 13
        # n-1+13 +1
        max_n = n + max_k
        dp = [[0] * (max_k + 1) for _ in range(max_n)]
        # 初始值，从0个位置中选出0个，只有一种方案
        dp[0][0] = 1
        # 预处理出 1 ~ n-1+13 的所有组合数
        for i in range(1, max_n):
            # 从任意个位置中选出0个，都只有一种方案
            dp[i][0] = 1
            for j in range(1, min(i, max_k) + 1):
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % mod

        # 预处理 2 ~ maxValue 的所有数x，将这些数分解出所有的质因子，然后记录各个质因子的个数k。
        # 由于并不关心个数k具体对应哪个质因子，所以使用数组记录个数k即可，而无需使用字典记录 个数k ——> 质因子
        ks = [[] for _ in range(maxValue + 1)]
        for i in range(2, maxValue + 1):
            # 质因子p从2开始：2、3、5、7、……
            p, x = 2, i
            # 不用担心会记录质因子4的个数，质因子4的个数一定为0，因为能被4整除，就一定能被2整除，x先被2整除过若干次后，直到不能被2整除，
            # 质因子p才会加1变成3，等质因子p加1变成4时，x都已经无法被2整除了，那就更不可能被4整除了，可理解为被2榨干了
            while p * p <= x:
                if x % p == 0:
                    k = 0
                    while x % p == 0:
                        k += 1
                        x //= p
                    ks[i].append(k)
                p += 1
            if x > 1:
                # 若最后榨完的x还大于1，则说明最后剩余的x本身就是个质因子，该质因子的个数为1
                ks[i].append(1)

        res = 0
        # 理想数组的结尾数字x可以为 [1, maxValue] 中的任意值
        for x in range(1, maxValue + 1):
            mul = 1
            # x为1时，由于1不存在质因子，所以ks[1]为空数组。长度为n、结尾数字为1的理想数组只有1个，即 全1数组
            for k in ks[x]:
                mul = mul * dp[n - 1 + k][k] % mod
            res = (res + mul) % mod
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

"""
 数论
分别考虑以x结尾长度为n的理想数组有多少个，数组结尾可以是1 ~ maxValue，因此把这些情况累加，就是最终结果。
以结尾为4、长度为5进行分析：
4的前面可以是4、2、1， 2的前面可以是2、1， 1的前面只能是1。例如：
[1, 2, 2, 4, 4]
[1, 1, 1, 4, 4]
[2, 2, 2, 4, 4]
[4, 4, 4, 4, 4]
以[1, 2, 2, 4, 4]为例，可以记为 [_, *2, _, *2, _]，只需记录在哪些位置的元素发生了改变(倍增)，
从当前倍增的位置开始 ~ 下一次倍增的位置之前(或数组结尾)，将会一直维持这个值。
可假设每个数组的开头前面有一个值1，若数组中的第一个元素为1，则没有发生倍增；若第一个元素不是1，则发生了倍增。
例如：[2, 2, 2, 4, 4] 可表示为 [*2, _, _, *2, _]；
在同一个位置可以发生多次倍增，例如：[1, 1, 1, 4, 4] 可表示为 [_, _, _, *2*2, _]；[4, 4, 4, 4, 4] 可表示为 [*2*2, _, _, _, _]。
由于固定了结尾为4，而4的质因子为2、2，即 4 = (1) * 2 * 2

//
所有结尾为4、长度为5的理想数组，问题可转化为 结尾数字(4)的质因子可以放在哪些位置，当前有5个不同的位置，2个质因子2，
//
从5个位置中选择一个(将2个2放在一个位置)或两个(将2个2放在不同位置)，因为2个2是相同的，谁先谁后，结果都是一样的。所以这是个组合问题。

//
问题进一步转化为：把k个相同的小球放进n个不同的盒子中，允许有些盒子为空，也允许一个盒子中放入多个小球，有多少种不同的放法？
//
该问题可用隔板法来求解，把n个盒子当做n-1个隔板，然后加上k个小球，相当于总共有 n-1 + k 个位置，从中选出n-1个位置放隔板，
即方案数为：C(n-1+k)(n-1)
由于maxValue <= 10^4，质因子最小为2，2^13 = 8192 < 10^4 < 16384 = 2^14，质因子越大，质因子的个数将会越小，
所以质因子为2时，质因子的个数k才能达到最大值13，即 k <= 13。所以上面的 C(n-1+k)(n-1) 可写为 C(n-1+k)(k) ，k 显然远小于n-1.
若结尾数字由多个不同的质因子组成，例如：k1个2、k2个3、k3个5，则可将问题分解为：
1、从n-1 + k1个位置中选出k1个位置放质因子2，得到 C(n-1+k1)(k1)
2、从n-1 + k2个位置中选出k2个位置放质因子3，得到 C(n-1+k2)(k2)
3、从n-1 + k3个位置中选出k3个位置放质因子5，得到 C(n-1+k3)(k3)
这3种情况之间互不影响：放质因子5的时候，不用关心这个位置之前放没放过2、3，以及放了多少个2、多少个3。
所以可采用乘法原理来计算最终结果：C(n-1+k1)(k1) * C(n-1+k2)(k2) * C(n-1+k3)(k3)

//
综上，原问题最终转化为：质因数分解出所有的质因子及其个数(其实只关注个数k) + 计算组合数问题
//
计算组合数问题 可用动态规划进行计算，假设dp[i][j] 表示从i个位置中选择j个，即 C(i)(j)。该问题可分为两种情况：
1、选择了位置i，则只需再从i-1个位置中选择j-1个，即 C(i-1)(j-1)
2、未选择位置i，则需要从i-1个位置中选择j个，即 C(i-1)(j)
所以，dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
"""
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

其他

2607. 使子数组元素和相等

难度中等13

给你一个下标从 0 开始的整数数组 arr 和一个整数 k 。数组 arr 是一个循环数组。换句话说，数组中的最后一个元素的下一个元素是数组中的第一个元素，数组中第一个元素的前一个元素是数组中的最后一个元素。

你可以执行下述运算任意次：

• 选中 arr 中任意一个元素，并使其值加上 1 或减去 1 。

执行运算使每个长度为 k 的 子数组 的元素总和都相等，返回所需要的最少运算次数。

子数组 是数组的一个连续部分。

示例 1：

输入：arr = [1,4,1,3], k = 2
输出：1
解释：在下标为 1 的元素那里执行一次运算，使其等于 3 。
执行运算后，数组变为 [1,3,1,3] 。
- 0 处起始的子数组为 [1, 3] ，元素总和为 4 
- 1 处起始的子数组为 [3, 1] ，元素总和为 4 
- 2 处起始的子数组为 [1, 3] ，元素总和为 4 
- 3 处起始的子数组为 [3, 1] ，元素总和为 4 
1
2
3
4
5
6
7
8

示例 2：

输入：arr = [2,5,5,7], k = 3
输出：5
解释：在下标为 0 的元素那里执行三次运算，使其等于 5 。在下标为 3 的元素那里执行两次运算，使其等于 5 。
执行运算后，数组变为 [5,5,5,5] 。
- 0 处起始的子数组为 [5, 5, 5] ，元素总和为 15
- 1 处起始的子数组为 [5, 5, 5] ，元素总和为 15
- 2 处起始的子数组为 [5, 5, 5] ，元素总和为 15
- 3 处起始的子数组为 [5, 5, 5] ，元素总和为 15
1
2
3
4
5
6
7
8

提示：

• 1 <= k <= arr.length <= 105
• 1 <= arr[i] <= 109

class Solution {
    // a[i] + a[i+1] + .. + a[i+k-1]
    // = a[i+1] + a[i+2] + .. + a[i+k]
    // ==> a[i] = a[i+k]

    // 按照i mod k 的结果将 arr 分组，对每一组（记为b）：
    // 让数组b的所有元素相等的最少运算次数：
    // 根据中位数贪心：将b的所有元素变为b的中位数是最优的
    // 裴蜀定理 ： 一个循环数组如果既有周期n，又有周期k，则必然有周期gcd(n,k)
    public long makeSubKSumEqual(int[] arr, int k) {
        int n = arr.length;
        k = gcd(k, n);
        long ans = 0;
        for(int i = 0; i < k; i++){
            List<Integer> list = new ArrayList<>();
            for(int j = i; j < n; j += k){
                list.add(arr[j]);
            }
            Collections.sort(list);
            int mid = list.get(list.size() / 2);
            for(int x : list){
                ans += Math.abs(x - mid);
            }
        }
        return ans;
    }

    public int gcd(int x, int y){
        return y == 0 ? x : gcd(y, x%y);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

提示：

• 1 <= k <= arr.length <= 105
• 1 <= arr[i] <= 109

class Solution {
    // a[i] + a[i+1] + .. + a[i+k-1]
    // = a[i+1] + a[i+2] + .. + a[i+k]
    // ==> a[i] = a[i+k]

    // 按照i mod k 的结果将 arr 分组，对每一组（记为b）：
    // 让数组b的所有元素相等的最少运算次数：
    // 根据中位数贪心：将b的所有元素变为b的中位数是最优的
    // 裴蜀定理 ： 一个循环数组如果既有周期n，又有周期k，则必然有周期gcd(n,k)
    public long makeSubKSumEqual(int[] arr, int k) {
        int n = arr.length;
        k = gcd(k, n);
        long ans = 0;
        for(int i = 0; i < k; i++){
            List<Integer> list = new ArrayList<>();
            for(int j = i; j < n; j += k){
                list.add(arr[j]);
            }
            Collections.sort(list);
            int mid = list.get(list.size() / 2);
            for(int x : list){
                ans += Math.abs(x - mid);
            }
        }
        return ans;
    }

    public int gcd(int x, int y){
        return y == 0 ? x : gcd(y, x%y);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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

难度中等23

给你一个长度为 n 下标从 0 开始的数组 nums ，数组中所有数字均为非负整数。对于 0 到 n - 1 之间的每一个下标 i ，你需要找出 nums 中一个 最小 非空子数组，它的起始位置为 i （包含这个位置），同时有 最大 的 按位或运算值 。

• 换言之，令 Bij 表示子数组 nums[i...j] 的按位或运算的结果，你需要找到一个起始位置为 i 的最小子数组，这个子数组的按位或运算的结果等于 max(Bik) ，其中 i <= k <= n - 1 。

一个数组的按位或运算值是这个数组里所有数字按位或运算的结果。

请你返回一个大小为 n 的整数数组 answer，其中 answer[i]是开始位置为 i ，按位或运算结果最大，且 最短 子数组的长度。

子数组 是数组里一段连续非空元素组成的序列。

示例 1：

输入：nums = [1,0,2,1,3]
输出：[3,3,2,2,1]
解释：
任何位置开始，最大按位或运算的结果都是 3 。
- 下标 0 处，能得到结果 3 的最短子数组是 [1,0,2] 。
- 下标 1 处，能得到结果 3 的最短子数组是 [0,2,1] 。
- 下标 2 处，能得到结果 3 的最短子数组是 [2,1] 。
- 下标 3 处，能得到结果 3 的最短子数组是 [1,3] 。
- 下标 4 处，能得到结果 3 的最短子数组是 [3] 。
所以我们返回 [3,3,2,2,1] 。
1
2
3
4
5
6
7
8
9
10

示例 2：

输入：nums = [1,2]
输出：[2,1]
解释：
下标 0 处，能得到最大按位或运算值的最短子数组长度为 2 。
下标 1 处，能得到最大按位或运算值的最短子数组长度为 1 。
所以我们返回 [2,1] 。
1
2
3
4
5
6

提示：

• n == nums.length
• 1 <= n <= 105
• 0 <= nums[i] <= 109

题解：https://leetcode.cn/problems/smallest-subarrays-with-maximum-bitwise-or/solution/by-endlesscheng-zai1/

该模板可以做到

1. 求出所有子数组的按位或的结果，以及值等于该结果的子数组的个数。
2. 求按位或结果等于任意给定数字的子数组的最短长度/最长长度。

思考：对于起始位置为 i 的子数组的按位或，至多有多少种不同的结果?

根据或运算的性质，我们可以从 a = nums[i] 开始，不断往右扩展子数组，按位或的结果要么使 a 不变，要么让 a 的某些比特位的值由0 变 1。最坏情况下从 x=0 出发，每次改变一个比特位，最终得到2^29 -1< 10^9，因此至多有 30 种不同的结果。这意味着我们可以递推计算所有按位或的结果。

另一个结论是，相同的按位或对应的子数组右端点会形成一个连续的区间，从而保证下面去重逻辑的正确性（这一性质还可以用来统计按位或结果及其对应的子数组的个数）。

据此， 我们可以倒着遍历 nums，在遍历的同时，用一个数组 ors 维护以 i 为左端点的子数组的按位或的结果，及其对应的子数组右端点的最小值。 继续遍历到 nums[i−1]时，我们可以把 nums[i−1] 和 ors 中的每个值按位或，合并值相同的结果。

这样在遍历时，ors中值最大的元素对应的子数组右端点的最小值，就是要求的最短子数组的右端点。

class Solution {
    public int[] smallestSubarrays(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        List<int[]> ors = new ArrayList<>(); // 按位或的值 + 对应子数组的右端点的最小值
        //倒着遍历 nums
        for(int i = n-1; i >= 0; i--){
            ors.add(new int[]{0, i});
            int j = 0;  // 原地去重
            for(int[] or : ors){ 
                or[0] |= nums[i]; // 和list中每一个数进行或操作
                if(ors.get(j)[0] == or[0]){
                    ors.get(j)[1] = or[1]; // 合并相同值，下标取最小的
                }else{
                    ors.set(++j, or);
                }
            }
            ors.subList(j+1, ors.size()).clear();
            // 本题只用到了 ors[0]，如果题目改成任意给定数值，可以在 ors 中查找
            res[i] = ors.get(0)[1] - i + 1;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

2654. 使数组所有元素变成 1 的最少操作次数

难度中等4

给你一个下标从 0 开始的 正 整数数组 nums 。你可以对数组执行以下操作 任意 次：

• 选择一个满足 0 <= i < n - 1 的下标 i ，将 nums[i] 或者 nums[i+1] 两者之一替换成它们的最大公约数。

请你返回使数组 nums 中所有元素都等于 1 的 最少 操作次数。如果无法让数组全部变成 1 ，请你返回 -1 。

两个正整数的最大公约数指的是能整除这两个数的最大正整数。

示例 1：

输入：nums = [2,6,3,4]
输出：4
解释：我们可以执行以下操作：
- 选择下标 i = 2 ，将 nums[2] 替换为 gcd(3,4) = 1 ，得到 nums = [2,6,1,4] 。
- 选择下标 i = 1 ，将 nums[1] 替换为 gcd(6,1) = 1 ，得到 nums = [2,1,1,4] 。
- 选择下标 i = 0 ，将 nums[0] 替换为 gcd(2,1) = 1 ，得到 nums = [1,1,1,4] 。
- 选择下标 i = 2 ，将 nums[3] 替换为 gcd(1,4) = 1 ，得到 nums = [1,1,1,1] 。
1
2
3
4
5
6
7

示例 2：

输入：nums = [2,10,6,14]
输出：-1
解释：无法将所有元素都变成 1 。
1
2
3

提示：

• 2 <= nums.length <= 50
• 1 <= nums[i] <= 106

题解：https://leetcode.cn/problems/minimum-number-of-operations-to-make-all-array-elements-equal-to-1/solution/liang-chong-fang-fa-bao-li-mei-ju-li-yon-refp/
如果nums中没有1，想办法花费尽量少的操作得出一个1由于只能操作相邻的数，所以这个1必然是一个连续子数组的GCD。(如果在不连续的情况下得到了1，那么这个1只能属于其中某个连续子数组，其余的操作是多余的。)
如何找到最短的连续子数组，这个子数组的gcd值为1？

方法一：暴力枚举每个区间，计算区间最小gcd值

class Solution {
    public int minOperations(int[] nums) {
        int n = nums.length, gcdAll = 0, cnt1 = 0;
        for(int x : nums){
            gcdAll = gcd(gcdAll, x); // 获得整个数组的gcd值
            if(x == 1) cnt1++;
        }
        if(gcdAll > 1) return -1; // 整个数组gcd != 1
        if(cnt1 > 0) return n - cnt1; // 1和其他数gcd = 1
        int minsize = n; // 找到最小的连续子数组，使其gcd=1
        // 暴力枚举每个区间
        for(int i = 0; i < n; i++){
            int g = 0;
            for(int j = i; j < n; j++){
                g = gcd(g, nums[j]); 
                if(g == 1){
                    minsize = Math.min(minsize, j-i+1);
                    break;
                }
            }
        }
        // 10 5 2 : n = 3
        // gcd(10,5)=5  : 5 5 2
        // gcd(5,2)=1   : 5 5 1
        // minsize-1次能操作出1，然后将数组剩下元素变成1 n-1
        // 操作次数 minsize-1 + n-1
        return minsize + n - 2;
    }

    public int gcd(int x, int y){
        return y == 0 ? x : gcd(y , x%y);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

方法二：利用gcd的性质（枚举数组的所有区间）

• 当枚举i位置时，更新以 (0,i] 位置为左端点的所有gcd值

class Solution {
    public int minOperations(int[] nums) {
        int n = nums.length, gcdAll = 0, cnt1 = 0;
        for(int x : nums){
            gcdAll = gcd(gcdAll, x); // 获得整个数组的gcd值
            if(x == 1) cnt1++;
        }
        if(gcdAll > 1) return -1; // 整个数组gcd != 1
        if(cnt1 > 0) return n - cnt1; // 1和其他数gcd = 1
        int minsize = n; // 找到最小的连续子数组，使其gcd=1
        
        /**
            GCD 要么不变，要么减半
            不同GCD的个数 = O(logU)
            2 6 3 4
            枚举 以i为结尾的区间的gcd
            g = [2]
            g = [2, 6]
            g = [1, 3, 3] = [1, 3]
            g = [1, 1, 4] = [1, 4]
            还要记录gcd上一次出现的下标（计算出子数组长度）
         */
        List<int[]> g = new ArrayList<int[]>(); // [GCD，相同 GCD 闭区间的右端点(最晚出现位置)]
        for(int i = 0; i < n; i++){
            for(int[] p : g) // 和list中每个数求一个gcd
                p[0] = gcd(p[0], nums[i]);
            g.add(new int[]{nums[i], i}); // 将当前元素加入list中

            int j = 0; // 去重，因为相同的 GCD 都相邻在一起
            for(int[] p : g){ // 去重采用双指针思想（如果相同j,p++，不相同j++,p++）
                if(g.get(j)[0] == p[0])
                    g.get(j)[1] = p[1];  // 合并相同值，下标取最小的（保留相同的两个数 右边数的下标）
                else{
                    g.set(++j, p); // 不相同，自增后保存p
                }
            }
            g.subList(j+1, g.size()).clear();

            if(g.get(0)[0] == 1){
                minsize = Math.min(minsize, i - g.get(0)[1] + 1);
            }
        }
        // 10 5 2 : n = 3
        // gcd(10,5)=5  : 5 5 2
        // gcd(5,2)=1   : 5 5 1
        // minsize-1次能操作出1，然后将数组剩下元素变成1 n-1
        // 操作次数 minsize-1 + n-1
        return minsize + n - 2;
    }

    public int gcd(int x, int y){
        return y == 0 ? x : gcd(y , x%y);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

原地去重版

class Solution {
    public int minOperations(int[] nums) {
        int n = nums.length, gcdAll = 0, cnt1 = 0;
        for(int x : nums){
            gcdAll = gcd(gcdAll, x); // 获得整个数组的gcd值
            if(x == 1) cnt1++;
        }
        if(gcdAll > 1) return -1; // 整个数组gcd != 1
        if(cnt1 > 0) return n - cnt1; // 1和其他数gcd = 1
        int minsize = n; // 找到最小的连续子数组，使其gcd=1
        
        /**
            GCD 要么不变，要么减半
            不同GCD的个数 = O(logU)
            2 6 3 4
            枚举 以i为结尾的区间的gcd
            g = [2]
            g = [2, 6]
            g = [1, 3, 3] = [1, 3]
            g = [1, 1, 4] = [1, 4]
            还要记录gcd上一次出现的下标（计算出子数组长度）
         */
        List<int[]> g = new ArrayList<int[]>(); // [GCD，相同 GCD 闭区间的右端点(最晚出现位置)]
        for(int i = 0; i < n; i++){
            g.add(new int[]{nums[i], i}); // 将当前元素加入list中
            int j = 0;// 原地去重，因为相同的 GCD 都相邻在一起
            for(int[] p : g){ // 和list中每个数求一个gcd
                p[0] = gcd(p[0], nums[i]);
                if(g.get(j)[0] == p[0])
                    g.get(j)[1] = p[1];  // 合并相同值，下标取最小的（保留相同的两个数 右边数的下标）
                else{
                    g.set(++j, p); // 不相同，自增后保存p
                }
            }
            g.subList(j+1, g.size()).clear();

            if(g.get(0)[0] == 1){
                minsize = Math.min(minsize, i - g.get(0)[1] + 1);
            }
        }
        // 10 5 2 : n = 3
        // gcd(10,5)=5  : 5 5 2
        // gcd(5,2)=1   : 5 5 1
        // minsize-1次能操作出1，然后将数组剩下元素变成1 n-1
        // 操作次数 minsize-1 + n-1
        return minsize + n - 2;
    }

    public int gcd(int x, int y){
        return y == 0 ? x : gcd(y , x%y);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

可以用该模板秒杀的题目

按位或：

• 898. 子数组按位或操作

按位与：

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

GCD：

• Codeforces 475D. CGCDSSQ
• Codeforces 1632D. New Year Concert

乘法：

蓝桥杯 2021 年第十二届国赛真题 - 和与乘积