如何计算一个非常大的数字(数字为1 mi的字符串)除以1500的余数

Question

我想知道数论是否有一个技巧可以在不需要实现BigInt除法的情况下计算这个余数。

Answer 1

哈哈，很简单！

我可以迭代所有数字，添加每个包裹。。。使用属性：

1） （a+b）mod c=（a mod c+b mod c）mod c

2） （a*b）mod c=（a mod c*b mod c）mod c

每走一步，10的幂可以增加1500。

Answer 2

它很简单，只需检查以下三件事：

可除以1500

1. 它必须可以被100整除（最后两位必须是00）
2. 它必须可以被5整除（从右边起的第三个数字必须是0或5）
3. 它必须能被3整除（迭代所有数字，求和，结果必须能被三整除）

如果你想知道剩余部分，它也很简单：

检查是否可被5整除并获得余数

1. 用500除后的最后4位得到余数，它将是从0到499

检查是否可被3整除并获得余数

2. 对所有数字进行迭代，求和，然后除以3得到余数，即从0到2。

3. 并且根据该余数将来自第一步的余数乘以该余数乘以CCD_ 10。

示例1

1234567890 % 1500 = 390

1. 7890 % 500 = 390
2. 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 0 = 45和45 % 3 = 0，所以不需要向390添加任何内容，结果就是390

示例2

12345678901 % 1500 = 901

1. 8901 % 500 = 401
2. 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 0 + 1 = 46和46 % 3 = 1，所以我们必须将1 * 500添加到第一步的结果中，所以401 + 1 * 500 = 901

示例3

1357913579 % 1500 = 1079

1. 3579 % 500 = 79
2. 1 + 3 + 5 + 7 + 9 + 1 + 3 + 5 + 7 + 9 = 50和50 % 3 = 2，所以我们必须将2 * 500添加到第一步的结果中，所以79 + 2 * 500 = 1079

希望这对你有帮助。