AcWing 870. 约数个数python3
原题链接
简单
作者:
xanxus1111
,
2020-06-02 15:34:32
,
所有人可见
,
阅读 583
# 约数个数:(a1+1)(a2+1)...(ak+1)
# 算术的基本定理又称为正整数的唯一分解定理,即:每个大于1的自然数,要么本身就是质数,要么可以写为2个或以上的质数的积,而且这些质因子按大小排列之后,写法仅有一种方式。
# 算术基本定理的内容由两部分构成:
# 分解的存在性:
# 分解的唯一性,即若不考虑排列的顺序,正整数分解为素数乘积的方式是唯一的。
# 约数定理
if __name__ == '__main__':
primes = {}
n = int(input())
for i in range(n):
x = int(input())
i = 2
while i <= x / i:
while x % i == 0:
x /= i
if i in primes:
primes[i] += 1
else:
primes[i] = 1
i += 1
if x > 1:
if x in primes:
primes[x] += 1
else:
primes[x] = 1
res = 1
mod = 1e9 + 7
for each in primes:
res = res * (primes[each] + 1) % mod
print(int(res))