摘要
Title: 871. 约数之和
Tag: 约数、约数之和
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

871. 约数之和

• 题意

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

• 思路

  求$(p^0 + p^1 + ... + p^{c})$
  可用递推式 ans = ans * p + 1

• 代码

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