Posts pythonTip 52 因子平方和
Post
Cancel

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(1) = 1^2\] \[f(2) = 1^2 + 2^2 \\\] \[f(3) = 1^2 + 3^2 \\\] \[f(4) = 1^2 + 2^2 + 4^2 \\\] \[f(5) = 1^2 + 5^2 \\\] \[f(6) = 1^2 + 2^2 + 3^2 + 6^2 \\\] \[f(7) = 1^2 + 7^2 \\\] \[f(8) = 1^2 + 2^2 + 4^2 + 8^2 \\\] \[f(9) = 1^2 + 3^2 + 9^2 \\\] \[f(10) = 1^2 + 2^2 + 5^2 + 10^2\]

我的第一个想法:使用循环的方式,依次累加求和。 这样的话,每个 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))
This post is licensed under CC BY 4.0 by the author.
Trending Tags
Contents

pythonTip 51 降序排序

pythonTip 53 神の安♂排

Trending Tags