如何取兩個非常大的數字的模數？

A是一個非常大的整數，它包含數字1只（例如：1111，1111111111111111）
B是一個非常大的整數（如：1231， 1231231823127312918923）

大，我的意思是1000位數。

2010-10-22 complez

這是作業嗎？ – 2010-10-22 17:14:53

不是，我通過了學齡：D。我要求我的朋友。 – complez 2010-10-22 17:18:07

這是你朋友的作業嗎？ – nmichaels 2010-10-22 17:23:08

1000個數字不是很大，使用任何大整數庫來獲得相當快的結果。如果你真的擔心性能，A可以寫成1111 ... 1 =（10 ⁿ -1）/ 9對於某些n，所以計算A mod B可以簡化爲計算（（10 ^）/ n-1）mod（9 * B））/ 9，並且您可以do that faster。

來源

2010-10-22 22:47:04 sdcvvc

若要計算一個數字模n，給定一個函數得到商和除以（n + 1）時的餘數，首先將數加1。然後，只要數字大於'n'，迭代：

number = (number div (n+1)) + (number mod (n+1))

最後在最後減去1。另一種方法是在開始時加一個，最後減1，檢查結果是否等於n，如果是，則返回零。

例如，給定由10來劃分的函數，可以計算12345678 MOD 9正是如此：

 
12345679 -> 1234567 + 9 
1234576 -> 123457 + 6 
    123463 -> 12346 + 3 
    12349 -> 1234 + 9 
    1243 -> 124 + 3 
    127 -> 12 + 7 
     19 -> 1 + 9 
     10 -> 1

減去1，結果是零。

來源

2010-10-22 17:59:41 supercat

那麼，這並不能真正幫助我們除以111111111111，是嗎？（除非我們已經有以111111111112爲基數的編號） – 2010-10-22 20:42:45

@Nikita Rybak：你沒有指定你的數字庫;因爲1111是二進制的特殊情況，但不是十進制的，我想也許你的數字是二進制的。 – supercat 2010-10-22 22:01:12

這不是我的電話號碼，它是由OP給出的:)另外，從他原來的帖子中可以看出，1111是紅利而不是除數。你提供了一個有趣的觀察，它似乎不適用於任務。 – 2010-10-22 22:08:14

1）只要找到一個執行任意精度算術的語言或包 - 在我的例子中，我會嘗試java.math.BigDecimal。

2）如果你自己這樣做，你可以避免必須使用加倍和減法進行除法。例如。 10 mod 3 = 10 - 3 - 3 - 3 = 1（重複減3直到你不能再有） - 這是非常慢的，所以雙3直到它小於10（例如到6），減去離開4，並重復。

來源

2010-10-23 05:04:02 mcdowella

試試蒙哥馬利減少如何找到大數模 - http://en.wikipedia.org/wiki/Montgomery_reduction

來源

2010-10-23 06:47:35 kuriouscoder

如何取兩個非常大的數字的模數？

回答

相關問題