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

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

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

回答

相关问题