37

我们知道

(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

4

4 回答 4

52

是的，但不一样：

(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

modb^(-1) mod p的模逆在哪里。对于, .bpp = primeb^(-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。

于 2012-09-02T10:39:46.537 回答
6

弗拉德的回答是正确的：

(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

这些和其他一些操作在等效部分中进行了概述。

只是想让您知道，这不仅适用于质数p。第一个适用于任何p. 第二个将适用于任何定义的p, whereb^(-1)或模逆。

模逆可以用扩展欧几里得算法计算

于 2016-02-23T23:30:09.687 回答
0

无论您的算法是什么，如果输入是 A 和 B 并且如果它们溢出，那么您将无法启动算法。告诉我们这些数字来自哪里很重要。它们是您拥有的其他数字的总和还是乘积？

对于大数，您必须为大数使用特殊的数学库。如何处理任意大的整数 有了这样的库，你可以只做 (A/B)%P。

于 2012-09-02T10:19:00.543 回答
0

以下是对两个数进行模除的另一种方法。

(A/B)%p = (A*modular_inverse(B))%p

Also , 
int modular_inverse(int n, int p){
    return power(n, p-2, p);
}

int power(ll x, ll i,ll p)
{
int ans = 1;
while(i > 0){
    if(i&1)ans = (ans*x)%p;
     i >>=1;
     x = (x*x)%p;
   }
return ans;
}
于 2021-09-08T23:09:29.893 回答