我们知道
(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时溢出
是的,但是有所不同:
(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
是模逆的b
MOD
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
。