java---约数个数（每日一道算法2022.9.10）

中秋快乐诸位~今天我被周赛暴杀了，很难受呜呜呜

注意事项：
代码中涉及分解质因数的算法，可以看我之前的文章：java—试除法分解质因数

题目：
给定 n 个正整数 ai，请你输出这些数的乘积的约数个数，答案对 1e9+7 取模

第一行包含整数 n
接下来 n 行，每行包含一个整数 ai
输出一个整数，表示所给正整数的乘积的约数个数，答案需对 1e9+7 取模

3
2
6
8
1
2
3
4

12
1

public class 约数_约数个数 {
    //mod是防止数值过大，primes存储每一个质因数出现几次
    public static long mod = 1000000007;
    public static HashMap<Integer, Integer> primes = new HashMap<>();
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        while (n-- > 0) {
            int x = in.nextInt();

            //这个地方用的是分解质因数的算法，稍微有所不同就是那个算法中我们每次都将出现次数输出，而这里我们是把出现次数存在map中
            //拿到x的质因数，并把每个质因数加到map的value值中，例如8的质因数是2*2*2，那么map中2的value值就会总共加3
            for (int i = 2; i <= x/i; i++) {
                while (x % i == 0) {
                    primes.put(i, primes.getOrDefault(i, 0) + 1);  //这一句用getOrDefault是防止NullPointerException
                    x /= i;
                }
            }
            if (x > 1) primes.put(x, primes.getOrDefault(x, 0) + 1);
        }
        
        //res存储最终结果，切记i+1，因为是从0次方到i次方
        long res = 1;
        for (Integer i : primes.values()) {
            res = (res * (i+1)) % mod;
        }
        System.out.println(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

公式：

我个人还是比较喜欢形象点的例子的：
比如360 = (2^3)*(3^2)*(5^1)
那么根据公式（a1+1）(a2+2)...(an+1)
360的约数个数就是：4*3*2 = 24个

原理其实也很好理解，就拿360来说，它分解为(2^3)*(3^2)*(5^1)
根据数学中的选择Selection方法，2这个位置有4种选择，分别2^0, 2^1, 2^2, 2^3
而当我们选择完2这个位置的时候，问题并没有结束，我们还需要继续选择3和5位置上的数，所以要将选择相乘
最后就得到4*3*2 = 24个
1
2
3
4
5
6
7
8
9

声明：算法思路来源为y总，详细请见https://www.acwing.com/
本文仅用作学习记录和交流