溢出錯誤的Python模塊化立方體

試圖解決這個問題：溢出錯誤的Python模塊化立方體

對於正數n，定義S（n）作爲整數x的針對1 < x < n和x^3 ≡ 1 mod n總和。

當n=91時，x有8個可能的值，即：9,16,22,29,53,74,79,81。因此，S(91)=9+16+22+29+53+74+79+81=363。

查找S（13082761331670030）。

當然，我的代碼適用於S(91)並試圖找到S(13082761331670030)當我得到兩個不同的錯誤。

這裏是我的代碼：

def modcube(n): 
    results = [] 
    for k in range(1,n): 
      if k**3%n==1: 
      results.append(k) 
    return results

這將產生Overflow error: range has too many items.當我嘗試使用「的xrange」而不是「範圍」我得到一個錯誤，說明蟒INT太大，轉換爲C長。我也嘗試過其他幾件事，但都沒有成功。

任何人都可以指向正確的方向，而不告訴我如何解決它？
請勿擾亂。我已經呆了兩天了，我的下一個選擇是嘗試在Java中實現這一點，因爲我是Python新手。

來源

2013-03-21 Melody

這可能會有幫助。您遇到的錯誤是數字太大而無法存儲在靜態類型中的結果。 http://stackoverflow.com/questions/1386604/handling-big-numbers-in-code。希望這是你正在尋找的細節水平。 – 2013-03-21 03:32:51

13 quadrillion是非常巨大的。我建議你尋找一種更有效的方式，通過尋找數學模式來編碼你的解決方案;） – Patashu 2013-03-21 03:34:45

你將無法用蠻力解決這個問題。如果你設法每秒處理一萬億次數據，它會花費你三個小時。 – Blender 2013-03-21 03:37:50

我認爲你需要了解這裏兩個概念：在C和Python中

的Python的使用被稱爲CPython的實施

1的整數表示，因爲它是用C寫的語言。在C中，長整數（通常）是32位長。這意味着它可以在-2147483647到2147483648之間使用整數。在Python中，當整數超過此範圍時，它將它們轉換爲任意精度整數，其中整數的大小僅受計算機內存的限制。但是，對這些任意整數（在Python中稱爲長整型）的操作比在32位整數上操作要慢幾個數量級。

2. range和xrange的區別：

range產生一個列表。如果您有range(10)，它將清單[0, 1, ... 9]完全存儲在內存中。這就是爲什麼在內存中存儲13082761331670030項目的列表太麻煩了。假設每個數字都是64位，那麼需要93TB的RAM來存儲整個列表！

xrange產生迭代器。它會逐個返回每個數字。這樣，它允許在列表的每個數字上執行操作，而無需將整個列表存儲在內存中。但是，再次，計算13082761331670030不同的數字可能需要更多的時間，你認爲...關於xrange的另一件事是它不適用於Python長整數;由於速度原因，它被限制爲32位整數。這就是爲什麼你的程序不能使用xrange。

底線：項目歐拉問題（或多或少）根據難度分類。你應該首先從較低的問題開始。

來源

2013-03-21 04:25:06

'xrange'參數可能受C'long'類型限制，例如'xrange（13082761331670030）'在我的64位系統上工作得很好。 – jfs 2013-03-21 05:49:58

python 3k does not have xrange – 2013-03-22 08:30:21

不，因爲'range'返回一個迭代器。但是因爲這個問題是關於'xrange'的，所以我認爲他使用的是Python 2。 – 2013-03-22 11:42:26

你想要提示，而不是解決方案。

提示：

考慮到的13082761331670030的prime factors等於以下的素數：2×3×5×7×11×13×17×19×23×29 X 31 X 37× 41×43
Chinese remainder theorem
僅僅因爲x^3 ≡ 1 mod n並不意味着有不大於3的其它滿足這個條件的其它值。具體來說，prime1 ** (prime2 - 2) % prime2

我的Python的解決方案是86毫秒...

來源

2013-03-21 05:51:07 dawg

溢出錯誤的Python模塊化立方體

回答

相關問題