我如何取两个非常大的数的模数？

Question

我需要A mod B的算法

1. A是一个非常大的整数,只包含数字1(例如:1111,111111111111111)
2. B是一个非常大的整数(例如:1231,1231231823127312918923)

大,我的意思是1000位数.

Answer 1

要计算数字mod n,给定一个函数来获得商和除以(n + 1)时的余数,首先在数字上加1.然后,只要数字大于'n',迭代:

number = (number div (n+1)) + (number mod (n+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,结果为零.

Answer 2

1000 位数字并不是很大，使用任何大整数库都可以获得相当快的结果。

如果你真的担心性能，对于某些 n，A 可以写为 1111...1=(10 ⁿ -1)/9，因此计算 A mod B 可以简化为计算 ((10^n-1) mod ( 9*B)) / 9，你可以做得更快。