避免求和，乘法溢出与模
Avoiding sum, multiplication overflow with modulo
我尝试解决一些简单的算法任务，但遇到了 modulo 操作的问题。
我需要计算这种操作：
(100003 - 200003*x + 300007*x*x*x) % 1000000
当然，300007*x*x*x 和 200003*x 都可以很容易地溢出 1000000，所以我需要 'make' modulo 所有部分。
我发现了这样的东西：Sum and multiplication modulo
并尝试“在每一步之后做一个 mod P”。像这样：
res = 100003
res = (100003 - 200003*x) % 1000000) % 1000000
...
对吗？因为我没有得到正确的结果。
要计算 (100003 - 200003*x + 300007*x*x*x) % 1000000 我会这样做：
- y = x % 1000000
- res = (100003 - (200003 * y) % 1000000 + (((300007 * y) % 1000000) * y) % 1000000) * y) % 1000000
- if (x > 0 && res < 0) res += 1000000
- if (x < 0 && res > 0) res -= 1000000
根据公式的书写方式，我们知道结果必须与 x 具有相同的符号。这可能是你出错的地方，你省略了第 3 步和第 4 步。尽管如前所述，使用 32 位它仍然会溢出。如果您需要正模，则可以省略第 4 步，如果 res 为负，则只需添加 1000000。
我尝试解决一些简单的算法任务，但遇到了 modulo 操作的问题。
我需要计算这种操作：
(100003 - 200003*x + 300007*x*x*x) % 1000000
当然，300007*x*x*x 和 200003*x 都可以很容易地溢出 1000000，所以我需要 'make' modulo 所有部分。
我发现了这样的东西：Sum and multiplication modulo 并尝试“在每一步之后做一个 mod P”。像这样：
res = 100003
res = (100003 - 200003*x) % 1000000) % 1000000
...
对吗？因为我没有得到正确的结果。
要计算 (100003 - 200003*x + 300007*x*x*x) % 1000000 我会这样做：
- y = x % 1000000
- res = (100003 - (200003 * y) % 1000000 + (((300007 * y) % 1000000) * y) % 1000000) * y) % 1000000
- if (x > 0 && res < 0) res += 1000000
- if (x < 0 && res > 0) res -= 1000000
根据公式的书写方式，我们知道结果必须与 x 具有相同的符号。这可能是你出错的地方，你省略了第 3 步和第 4 步。尽管如前所述，使用 32 位它仍然会溢出。如果您需要正模，则可以省略第 4 步，如果 res 为负，则只需添加 1000000。