pythonTip 52 因子平方和

题目描述： 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) 的值.

示例：

输入：N = 1

输出：1

分析: 先假设 N = 10.

那么 \(F(10) = f(1) + f(2) + f(3) + f(4) + f(5) + f(6) + f(7) + f(8) + f(9) + f(10)\) 又:

我的第一个想法：使用循环的方式，依次累加求和。 这样的话，每个 f(i) 就只运算一次了。开开心心去提交，结果就是超时了，然后我就开始怀疑人生，这都能超时，是不是题目有问题？但是又看到别人都通过了，想想应该是自己不行，但是男人怎么能不行呢！ 我开始观察。

以前我做质数筛的时候，是通过找因子的方式，确定一个数是不是质数。

后来做质数筛的时候，是通过放大因子的倍数直接去掉 非质数。

然后我就联想到了这里，nice。 我就开开心心的整理出又一份代码，如下：

1
2
3
4
5
6

res = 0

for key in range(1, N+1):
    res += (key*key) * (N//key)

print(res)

结果又是超时。这特喵的就有点小气了，这还要怎么优化嘛，一共就几行代码。

代码不能优化，那就优化思路。

我们做质数筛的时候，也不用循环到最大值，往往是最大值一半，或者是开根号就ok了。 于是我就想，通过因子放大的方式，我已经可以确定很多数的因子。

然后剩下的就是大于 最大值一半的值, 也就是这里的 6, 7, 8, 9, 10 ，然后我就想，我可以先用因子放大的方式，求所有因子的和，然后再单独计算 6, 7, 8, 9, 10 的平方和。

然后我有卡住了，这要怎么算啊，如果是循环的方式，那不就和之前的一样了吗，可能会有公式，我就去百度了一下。平方和公式

\(1^2 + 2^2 + 3^2 +....+n^2 = [n*(n+1)*(2n+1)] /6\) 那这要怎么算后一半的平方和呢？ 想了一下，没有想到，于是干脆就让前面每一次的循环少加一次。就有了最终的代码。

代码:

1
2
3
4
5
6
7
8
9
10

def main(n):
    res = 0
    
    for key in range(1, n//2+1):
        # 这里的 n//key-1 就是为了 筹平方和公式。
        res += (key*key) * (n//key-1)
        
    res += (n*(n+1)*(2*n+1))//6
    return res
print(main(N))