模塊化立方體

我有解決這個問題的困難：模塊化立方體

對於正數n，定義C（n）的作爲整數x的數，其中1 < X < n和x^3 = 1 mod n。

當n = 91時，對於x有8個可能值，即：9,16,22,29,53,74, 79,81。因此，C（91）= 8。

找到正數的總和 ñ< = 10^11，其在C（n）= 242

我的代碼：

double intCount2 = 91; 
double intHolder = 0; 

for (int i = 0; i <= intCount2; i++) 
{ 
    if ((Math.Pow(i, 3) - 1) % intCount2 == 0) 
    { 
     if ((Math.Pow(i, 3) - 1) != 0) 
     { 
      Console.WriteLine(i); 
      intHolder += i; 
     } 
    } 
} 
Console.WriteLine("Answer = " + intHolder); 
Console.ReadLine();

本工程爲91，但是當我用大量的0代替大量的數據，它給了我很多我知道是錯誤的答案。我認爲這是因爲它非常接近於零，它只是舍入到0。有什麼方法可以查看某個值是否恰好爲0？或者我的邏輯錯了？

我知道我需要一些優化來獲得這個提供及時的答案，但我只是試圖讓它產生正確的答案。

來源

2010-01-12 Hazior

什麼intCount2你的最小值知道給出錯誤的結果？ – 2010-01-12 14:49:55

@JonB：91「這適用於91但是......」 – Hazior

但不是什麼？ 92看起來貌似合理。 – 2010-01-12 15:09:03

讓我把你的問題推廣到兩個任務離子：

1）這個程序有什麼特別的錯誤？

2）如何找出程序中的問題所在？

別人已經回答了第一部分，但要總結：

問題1：Math.Pow採用雙精度浮點數，這是隻精確到大約15位小數。他們不適合做需要完美準確性的問題，涉及大整數。如果你試圖在雙打中計算1000000000000000000 - 1，你會得到1000000000000000000，這是對小數點後15位的精確答案;這就是我們所保證的。如果你需要一個完全準確的答案來處理大數量的問題，那麼使用long的結果少於約100億，或者System.Numerics中的大整數數學類將隨下一個版本的框架一起提供。

問題2：有更高效的方法來計算不涉及生成巨大數字的模指數;使用它們。

但是，我們在這裏得到的是一個「給男人一條魚」的情況。最好是教你如何釣魚;學習如何使用調試器來調試程序。

如果我有調試這個節目，我會做的第一件事是重寫它，以便沿途的每一步都被存儲在一個局部變量：

double intCount2 = 91; 
double intHolder = 0; 

for (int i = 0; i <= intCount2; i++) 
{ 
    double cube = Math.Pow(i, 3) - 1; 
    double remainder = cube % intCount2; 
    if (remainder == 0) 
    { 
     if (cube != 0) 
     { 
      Console.WriteLine(i); 
      intHolder += i; 
     } 
    } 
}

現在通過它一步在調試器與例如你知道答案是錯誤的，並尋找違反你的假設的地方。如果你這樣做，你會很快發現1000000立方體減1不是99999999999999999，而是1000000000000000000.

所以這是建議＃1：編寫代碼，以便它可以輕鬆地在調試器中穿過，並檢查每一步都在尋找那個看起來不對的人。

建議＃2：注意安靜的嘮叨疑惑。當某些東西看起來不合時宜或有一點你不明白時，調查一下，直到你明白它爲止。

來源

2010-01-12 16:57:27

維基百科上有關於Modular exponentiation的文章，您可能會發現內容豐富。 IIRC，Python有它的內置。C＃沒有，所以你需要自己實現它。

來源

2010-01-12 14:08:55 Brian

不要使用Math.Pow來計算功率模n;您可能會遇到其他可能的問題溢出問題。相反，你應該從第一原則來計算它們。因此，爲了計算一個整數i模的立方n第一減少i模n一些整數j使得i是全等j模n和0 <= j < n。然後在每次乘法之後迭代乘以j並減少模n;要計算一個立方體，你會執行這個步驟兩次。當然，這是本地方法，但您可以通過使用exponentiation by squaring遵循經典的求冪運算法則來提高效率。

此外，就效率而言，我注意到您不必要地計算Math.Pow(i, 3) - 1兩次。因此，在最低限度，替代

if ((Math.Pow(i, 3) - 1) % intCount2 == 0) { 
    if ((Math.Pow(i, 3) - 1) != 0) { 
     Console.WriteLine(i); 
     intHolder += i; 
    } 
}

與

int cubed = Math.Pow(i, 3) - 1; 
if((cubed % intCount2 == 0) && (cubed != 0)) { 
    Console.WriteLine(i); 
    intHolder += i; 
}

來源

2010-01-12 14:14:07 jason

嘛，有什麼東西丟失或錯字......

「intHolder1」應該大概是「的IntHolder」和intCount2 = 91導致8增量行應該是： -

intHolder ++;

來源

2010-01-12 15:07:09

我沒有一個解決問題的方法，但這裏只是一個忠告：

不要使用浮點數計算，僅涉及整數...類型int（Int32 ）顯然不足以滿足您的需求，但long（Int64）應該足夠了：您將必須操縱的最大數字將是(10^11 - 1)^3，它小於10^14，這肯定小於Int64.MaxValue。優點：
- 你做的64位整數，這應該是在64位處理器
- 所有的計算結果是準確的相當有效，因爲存在由於內部沒有任何近似的所有計算雙打的表現

不要使用Math.Pow來計算一個整數的立方體...... x*x*x是一樣簡單，更高效，因爲它不需要轉換到/從雙。無論如何，我不是在數學很好，但你可能並不需要計算X^3 ...查看關於模冪的鏈接在其他的答案

來源

2010-01-12 21:00:29

模塊化立方體

回答

相關問題