algorithm - 计算 3 个数字模 m 的乘积

Question

给定整数a、b、c和m，我需要计算(a*b*c)%m，其中a、b、c和m可以大到10^18 。我知道如何计算 (a*b)%m 如下:

unsigned long long mulmod(unsigned long long a,unsigned long long b,unsigned long long c){
unsigned long long x = 0,y=a%c;
while(b > 0){
    if(b%2 == 1) {
        x = (x+y)%c;
    }
    y = (y*2)%c;
    b /= 2;
}
return x%c;

}

可以对(a*b*c)%m做这样的事情吗？

Answer 1

假设您的函数 mulmod(a, b, m) 在返回 (a * b)/m 提醒的位置工作。您可以通过 mulmod(mulmod(a, b, m), c, m)

计算 (a * b * c) % m

你可能会问为什么它会起作用？为什么(a * b * c) % m等于((a * b) % m) * c % m。可以证明如下:

让

Let          a * b = dm + r
             c     = em + q
Therefore,   a * b * c = (dm + r) * (em + q)
                       = (dem + dq + er)m + rq

So           (a * b * c) % m = [(de + r + q)m + rq] % m 
                             = rq % m

How about    [(a * b) % m] * c % m
We know that (a * b) % m = r
Therefore    [(a * b) % m] * c % m = [r * (em + q)] % m
                                   = (rem + rq) % m
                                   = rq % m

Hence, [(a * b) % m] * c % m and (a * b * c) % m are the same