AcWing 871. 约数之和-python
原题链接
简单
作者:
Actor丶
,
2020-04-09 17:09:58
,
所有人可见
,
阅读 1240
"""
基本思想:
如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数: (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和: (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)
步骤:
1. 对N进行隐式分解(试除法)
2. 根据公式计算约数之和
"""
from collections import defaultdict
def divide(x):
"""对x进行因式分解"""
if x<2:
return
i = 2 # 质数是大于1的自然数,所以从2开始遍历
while i<=x/i:
while x%i==0:
x=int(x/i)
primes[i] += 1
i+=1 #!!!出错:循环忘记i+1了,导致死循环
if x>1: # 根据一个数n最多只包含一个大于sqrt(n)的质数,所以x>1,表示x是这个大的质数
primes[x] += 1
if __name__=="__main__":
n = int(input().strip())
mod = int(1e9+7) # !!!出错,这里默认是浮点数,必须要转换成整数mmb
primes = defaultdict(int) # 存储因式分解的结果
for _ in range(n):
a = int(input().strip())
# 1. 对a分解质因数
divide(a)
res = 1
# 2. 根据公式计算约数的个数
for k,v in primes.items(): # k是底数,v是指数;!!!注意:遍历时要使用primes.items()
t = 1
while v:
t = (k*t+1)
v -= 1
res = (res*t)
print(int(res % mod))
python 为什么不能在运行的时候取模。为什么取了就报错了啊。。