題目

來(lái)源于 PythonTip 。

            
              6 的因子有 1, 2, 3 和 6, 它們的平方和是 1 + 4 + 9 + 36 = 50. 如果 f(N) 代表正整數(shù) N 所有因子的平方和, 那么 f(6) = 50.
現(xiàn)在令 F 代表 f 的求和函數(shù), 亦即 F(N) = f(1) + f(2) + .. + f(N), 顯然 F 一開(kāi)始的 6 個(gè)值是: 1, 6, 16, 37, 63 和 113.
那么對(duì)于任意給定的整數(shù) N (1 <= N <= 10^8), 輸出 F(N) 的值.

            
          

解析

根據(jù)題目要求一步一步來(lái)，可以實(shí)現(xiàn)該功能，但是考慮到實(shí)際 N 值的大小，程序時(shí)間復(fù)雜度會(huì)變得極大，因此需要從代碼層面進(jìn)行優(yōu)化。

在優(yōu)化之前首先需要了解一下平方和的計(jì)算， 計(jì)算1到100的平方的和

平方求和公式：

代碼實(shí)現(xiàn)：

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

            
          

接著分析本題目，在原始方法不可取的情況下，對(duì)數(shù)據(jù)進(jìn)行規(guī)律分析。

列出從 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

            
          

輸出結(jié)果為：

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

            
          

發(fā)現(xiàn) 1 有 6 個(gè)，2 有 3 個(gè)，3 有 2 個(gè)。。。替換 N 值，依然可以發(fā)現(xiàn)此現(xiàn)象。
總結(jié) F(N)==1^2*(N//1)+2^2*(N//2)+...+N^2*(N//N)

得到改進(jìn)版如下：

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

            
          

但是時(shí)耗依然很大，對(duì)于每個(gè)數(shù)平方需要乘積的次數(shù) N//i 進(jìn)行分析。

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

            
          

結(jié)果為：

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

            
          

測(cè)試發(fā)現(xiàn)后半部分的個(gè)數(shù)都是 1，所以對(duì)之前的程序進(jìn)行修改。

            
              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)

            
          

這里運(yùn)用到了平方和求差公式，我們需要計(jì)算 6**2*1+5**2*1+4**2*1 ，即可簡(jiǎn)化為 sumsqr(6)-sumsqr(3) 。
提交程序后，運(yùn)行時(shí)耗依然很大，不通過(guò)。那就需要對(duì)循環(huán)再次進(jìn)行簡(jiǎn)化，也就是對(duì)循環(huán)次數(shù) N//2 進(jìn)行壓縮，那么我們?cè)倏匆幌律鲜銎椒胶统朔e次數(shù)。

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

            
          

和 N 相關(guān)的數(shù)值，除了 N//2 平均數(shù)，那就只有 sqrt(N) 平方根，這兩個(gè)是比較常見(jiàn)的數(shù)值。
L2 中的 1 一直到最后，2 到第三項(xiàng)，恰好 sqrt(6) 為 2 代表第二項(xiàng)，所以第三項(xiàng)之后的可以用平方差進(jìn)行求和計(jì)算。 3**2*2+4**2*1+5**2*1+6**2*1 = （3**2）+ （3**2+4**2+5**2+6**2） ，再進(jìn)一步轉(zhuǎn)換為 F(6)=1+2**2*3+sumsqr(6)-sumsqr(2)+sumsqr(3)-sumsqr(2) ，進(jìn)而得到以下代碼：

            
              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

            
          

最后提交代碼成功，時(shí)間復(fù)雜度也是最低的。