我们知道
(A + B) % P = (A % P + B % P) % P (A * B) % P = (A % P * B % P) % P
P素数在哪里？
P
我需要计算(A / B) % P哪里A,B可能很大并且可能溢出。
(A / B) % P
A,B
这样的模块化算术公式对(A / B) % P和成立(A - B) % P。
(A - B) % P
如果不是，请说明正确答案。
即是真的(A / B) % P = ((A % P) / (B % P)) % 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时溢出
是的，但是有所不同：
(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。
b^(-1) mod p
b
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。
N or N^2+5
2
3
(a*b) mod P
