摘要
Title: 870. 约数个数
Tag: 约数、约数个数
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

870. 约数个数

• 题意

  给定 n 个正整数 ai，请你输出这些数的乘积的约数个数，答案对 10^9+7 取模。

• 思路

  如果 $N = {p1}^{c1} * {p2}^{c2} * ... *{pk}^{ck}$ (p是质因子)
  约数个数： $(c1 + 1) * (c2 + 1) * ... * (ck + 1)$
  约数之和： $(p1^0 + p1^1 + ... + p1^{c1}) * ... * (pk^0 + pk^1 + ... + pk^{ck})$

  ps: 约数个数： 每个幂都是 0 ~ ck, 共ck + 1个
  所有int范围的约数个数最多大约1500个

• 代码

  MOD = int(1e9 + 7)
  from collections import Counter
  d = Counter()
  for _ in range(int(input())):
      n = int(input())
      i = 2
      while i <= n // i:
          while n % i == 0:
              n //= i
              d[i] += 1
          i += 1
      if n > 1:
          d[n] += 1
  ans = 1
  for key in d.keys():
      ans = ans * (d[key] + 1) % MOD
  print(ans)