一尘不染
阅读 263
2020-07-28
两数除法模
algorithm我们知道
(A + B) % P = (A % P + B % P) % P
(A * B) % P = (A % P * B % P) % P
P素数在哪里？
我需要计算(A / B) % P哪里A,B可能很大并且可能溢出。
这样的模块化算术公式对(A / B) % P和成立(A - B) % P。
如果不是，请说明正确答案。
即是真的(A / B) % P = ((A % P) / (B % P)) % P吗？
我正在尝试计算（N *（N ^ 2 + 5）/ 6）％P，其中N可以大到10 ^ 15
这里A = n *（n ^ 2 + 5）肯定会在n = 10 ^ 15时溢出
阅读 263
2020-07-28
共1个答案
一尘不染
是的，但是有所不同：
(a - b) mod p = ((a mod p - b mod p) + p) mod p
(a / b) mod p = ((a mod p) * (b^(-1) mod p)) mod p
哪里b^(-1) mod
p是模逆的bMOD
p。对于p = prime，b^(-1) mod p = b^(p - 2) mod p。
编辑：
（N *（N ^ 2 + 5）/ 6）％P
您不需要任何模块化逆函数。只是简化分数：N or N^2+5将被2和整除3。因此，将它们分开，然后就可以了(a*b) mod P。
2020-07-28