Python 求解因子平方和

hresh 620 0

Python 求解因子平方和

题目

来源于 PythonTip 。

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到100的平方的和

平方求和公式:

Python 求解因子平方和

代码实现:

def sumsqr(n):
    return int(n * (n + 1) * (2 * n + 1) / 6)
print(sumsqr(100))

接着分析本题目,在原始方法不可取的情况下,对数据进行规律分析。

列出从 1 到 N 的因子列表。

N = 6
def get_factors(n):
    dp = []
    for i in range(1, n + 1):
        if n % i == 0:
            dp.append(i)
    return dp


def cal_sums():
    global N
    dp = []
    for i in range(1, N + 1):
        dp.append(get_factors(i))
    return dp

输出结果为:

[[1], [1, 2], [1, 3], [1, 2, 4], [1, 5], [1, 2, 3, 6]]

发现 1 有 6 个,2 有 3 个,3 有 2 个。。。替换 N 值,依然可以发现此现象。
总结 F(N)==1^2*(N//1)+2^2*(N//2)+...+N^2*(N//N)

得到改进版如下:

N = 6
s = 0
for i in range(1,N+1):
    s = s + i**2*(N//i)
print (s)

但是时耗依然很大,对于每个数平方需要乘积的次数 N//i 进行分析。

N = 10
L1 = list(range(1,N+1))
L2 = [N//i for i in L1]
print (L1)
print (L2)

结果为:

[1, 2, 3, 4, 5, 6]
[6, 3, 2, 1, 1, 1]

测试发现后半部分的个数都是 1,所以对之前的程序进行修改。

N = 6
s = 0
for i in range(1,N//2+1):
    s = s + i**2*(N//i)

def sumsqr(n):
    return int(n*(n+1)*(2*n+1)/6)
s = s + (sumsqr(N) - sumsqr(N//2))

print (s)

这里运用到了平方和求差公式,我们需要计算 6**2*1+5**2*1+4**2*1,即可简化为 sumsqr(6)-sumsqr(3)
提交程序后,运行时耗依然很大,不通过。那就需要对循环再次进行简化,也就是对循环次数 N//2 进行压缩,那么我们再看一下上述平方和乘积次数。

[1, 2, 3, 4, 5, 6]
[6, 3, 2, 1, 1, 1]

和 N 相关的数值,除了 N//2 平均数,那就只有 sqrt(N) 平方根,这两个是比较常见的数值。
L2 中的 1 一直到最后,2 到第三项,恰好 sqrt(6) 为 2 代表第二项,所以第三项之后的可以用平方差进行求和计算。3**2*2+4**2*1+5**2*1+6**2*1 = (3**2)+ (3**2+4**2+5**2+6**2),再进一步转换为F(6)=1+2**2*3+sumsqr(6)-sumsqr(2)+sumsqr(3)-sumsqr(2),进而得到以下代码:

def sumsqr(n):
    return int(n * (n + 1) * (2 * n + 1) / 6)

def factors_sums():
    N = 6
    s = 0
    m = int(sqrt(N))
    i = 1
    while i <= m:
        s += pow(i,2)*(N//i)
        s += sumsqr(N//i) - sumsqr(m)
        i += 1
    return s

最后提交代码成功,时间复杂度也是最低的。

发表评论 取消回复
表情 图片 链接 代码

分享