如何计算除以 1500 后的一个非常大的数字（具有 1 mi 数字的字符串）的余数

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

十的次方可以增加mod每步1500。

Answer 2

很简单，只需检查这三件事：

1500的整除率

1. 它必须能被 100 整除（最后两位数字必须是 00）
2. 它必须能被 5 整除（右起第三位数字必须是 0 或 5）
3. 它必须能被 3 整除（遍历所有数字，求和，结果必须能被 3 整除）

如果你想知道余数，它又很简单：

检查是否能被 5 整除并求余数

1. 取500后4位的余数，就是0到499。

检查是否能被 3 整除并求余数

2. 遍历所有数字，求和，除以3后得到余数，就是0到2。

3. 并根据此余数将第一步的余数乘以此余数乘以 500。

示例 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.

希望对您有所帮助。