Wu Yudong's Blog

问题描述:

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个1²，N//2个2²，N//3个3²…，N//N个N²的和。

首先试一下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*1² + 3*2² +2*3²) + (4²+5²+6²)

使用平方和公式：1²+2²+…+n²=n*(n+1)*(2n+1)/6

result = (6*1² + 3*2² +2*3²) + (4²+5²+6²) = (6*1² + 3*2² +2*3²) + (1²+2²+3²+4²+5²+6²) — (1²+2²+3²)

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

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

继续发现规律：为了方便查看，我们用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*1²+5²+6²+..+16²) + (8*2²+ 5²+6²+7²+8²)+(5*3²+5²)+4*4²

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

也就是有每个部分的值都为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