目的

求一个数的所有约数的个数

原理

利用分解质因数的原理：
n = p1``a1`` p2``a2`` p3``a3``... pk``ak

那么 n 所有的约数都可以用这些个质数来表示
n的一个约数可以表示为 p1``b1`` p2``b2`` p3``b3`` ... pk``bk
相当于是所有指数的组合问题
b1 能取到 0~a1
…
bk 能取到 0~ak
故 count(n) = (a1 + 1) * (a2 + 1) * ... * (ak + 1)

870. 约数个数
给定 n 个正整数 ai，请你输出这些数的乘积的约数个数，答案对 109+7取模。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个整数 ai。
输出格式
输出一个整数，表示所给正整数的乘积的约数个数，答案需对 109+7 取模。
数据范围
1≤n≤100
1≤ai≤2×109
输入样例：

  1. 3
  2. 2
  3. 6
  4. 8

输出样例：

  1. 12

时间复杂度O(nsqrt(n))
代码：

  1. import java.util.*;
  3. public class Main {
  4.     static final int MOD = 1000000007;
  6.     public static void main(String[] args) {
  7.         Scanner sc = new Scanner(System.in);
  9.         int n = sc.nextInt();
  11.         Map<Integer, Integer> map = new HashMap<>();
  12.         while (n-- > 0) {
  13.             int x = sc.nextInt();
  15.             for (int i = 2; i <= x / i; i++) {
  16.                 while (x % i == 0) {
  17.                     int cnt = map.getOrDefault(i, 0);
  18.                     map.put(i, cnt+1);
  19.                     x /= i;
  20.                 }
  21.             }
  22.             if (x > 1) map.put(x, map.getOrDefault(x, 0) + 1);
  23.         }
  25.         long res = 1;
  26.         for (int key : map.keySet()) {
  27.             int a = map.get(key);
  28.             res = res * (a + 1) % MOD;
  29.         }
  30.         System.out.println(res);
  31.     }
  32. }

注意 res 一定要取 long 类型，不然会溢出造成错误。