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 + qTherefore,   a * b * c = (dm + r) * (em + q)                       = (dem + dq + er)m + rqSo           (a * b * c) % m = [(de + r + q)m + rq] % m                              = rq % mHow about    [(a * b) % m] * c % mWe know that (a * b) % m = rTherefore    [(a * b) % m] * c % m = [r * (em + q)] % m                                   = (rem + rq) % m                                   = rq % mHence, [(a * b) % m] * c % m and (a * b * c) % m are the same