亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

Python 求解因子平方和

系統 2527 0

題目

來源于 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的平方的和

平方求和公式:
在這里插入圖片描述
代碼實現:

            
              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

            
          

最后提交代碼成功,時間復雜度也是最低的。


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 麻豆精品| 国产不卡在线看 | 思思久久99热这里只有精品66 | 99视频免费在线观看 | 亚洲精品麻豆一区二区 | 成人欧美精品一区二区不卡 | 国产色视频一区 | 精品久久久久久久久久中文字幕 | 亚洲片在线观看 | 伊人久久成人 | 亚洲尹人香蕉网在线视颅 | 亚洲天堂一区在线 | 看全色黄大色黄大片 视 | 欧美一级毛片免费看视频 | 日韩女人做爰大片 | 国产精品第一页爽爽影院 | 日本一区二区三区在线播放 | a毛片毛费观看 | 亚洲国产精品久久婷婷 | 久久精品三级 | 久热这里只精品99re8久 | 韩国一级特黄毛片大 | 亚洲美女激情视频 | 欧美成人免费一区在线播放 | 国产一区二区视频在线播放 | 天天拍拍天天爽免费视频 | 手机看片福利 | 夜夜女人国产香蕉久久精品 | 日本不卡中文字幕一区二区 | 四虎色影院 | 国产在线一区二区三区在线 | 国产精品成人在线播放 | 草久视频在线 | 国产三级做爰高清视频a | 在线观看人成网站深夜免费 | 久久美剧 | 免费一级大片儿 | 亚洲视频www | 精品国产91乱码一区二区三区 | 天天做天天添天天谢 | 中文字幕精品视频 |