目的

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

原理

利用分解质因数的原理:
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.*;
  2. public class Main {
  3. static final int MOD = 1000000007;
  4. public static void main(String[] args) {
  5. Scanner sc = new Scanner(System.in);
  6. int n = sc.nextInt();
  7. Map<Integer, Integer> map = new HashMap<>();
  8. while (n-- > 0) {
  9. int x = sc.nextInt();
  10. for (int i = 2; i <= x / i; i++) {
  11. while (x % i == 0) {
  12. int cnt = map.getOrDefault(i, 0);
  13. map.put(i, cnt+1);
  14. x /= i;
  15. }
  16. }
  17. if (x > 1) map.put(x, map.getOrDefault(x, 0) + 1);
  18. }
  19. long res = 1;
  20. for (int key : map.keySet()) {
  21. int a = map.get(key);
  22. res = res * (a + 1) % MOD;
  23. }
  24. System.out.println(res);
  25. }
  26. }

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