guangzhou



shanghai

Recent posts:
Blog index
About
RSS

因子平方和问题

January 14, 2017     Algorithm   696   

问题描述:

6 的因子有 1, 2, 3 和 6, 它们的平方和是 1 + 4 + 9 + 36 = 50. 如果 f(N) 代表正整数 N 所有因子的平方和, 那么 f(6) = 50. 现在令 F 代表 f 的求和函数, 亦即 F(N) = f(1) + f(2) + .. + f(N), 显然 F 一开始的 6 个值是: 1, 6, 16, 37, 63 和 113. 那么对于任意给定的整数 N (1 <= N <= 10^8), 输出 F(N) 的值.

这个题直接解答的代码很简洁:

print sum(sum(i**2 for i in range(1,N+1) if N%i==0) for N in range(1,N+1))

但毫无疑问超时了,只能发现规律来优化

我们可以发现其实F(N)就是N个12,N//2个22,N//3个32…,N//N个N2的和。

首先试一下6,发现一个规律:

因子数字:1 2 3 4 5 6
因子个数:6 3 2 1 1 1

可以记为:value = (1,2,3,4,5,6),而且num=[6,3,2,1,1,1],其实我们可以发现,后面有一半的个数数字都是1的,也就是分别各有1个4,5,6

因此可以分为两部分来算,result = (6*12 + 3*22 +2*32) + (42+52+62)

使用平方和公式:12+22+…+n2=n*(n+1)*(2n+1)/6

result = (6*12 + 3*22 +2*32) + (42+52+62) = (6*12 + 3*22 +2*32) + (12+22+32+42+52+62) — (12+22+32)

这样就可以减少一些计算量

最后发现还是超时了!!!

继续发现规律:为了方便查看,我们用N=16

value = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16],num = [16, 8, 5, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] ;

可以发现,在数字比平方根大的个数(也就是value从5开始)的个数有一个规则就是个数是从大到小的,而且是均匀的;所以我们可以与前面的分开计算;

比如F(16) = (16*12+52+62+..+162) + (8*22+ 52+62+72+82)+(5*32+52)+4*42

我们可以发现一个规则就是每一个分部都是N//i*i2+((N**0.5+1)2+…+(N//i)2)

也就是有每个部分的值都 为N//i*i^2+((1^2+2^2+..+(N//i)^2) – ((1^2+2^2+…+N**0.5^2))

代码如下:

def sumsqr(value):  # 计算1~n的平方和
    return value * (value+1)*(2*value + 1) / 6

rsl = 0
sqr = int(N**0.5)
for i in range(1, sqr+1):
    rsl += i ** 2 * (N // i) + sumsqr(N//i) - sumsqr(sqr)
print rsl

 

如果文章对您有帮助,欢迎点击下方按钮打赏作者

Comments

No comments yet.
To verify that you are human, please fill in "七"(required)