計算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 

Answer 2

乘法屬性模運算如下：

ab mod m = (a mod m)(b mod m) mod m       // Rule 1 

由此可以得出：

abc mod m = (ab mod m)(c mod m) mod m      // Expand (ab)c mod m 
      = ((a mod m)(b mod m) mod m mod m)(c mod m) mod m // Expand ab mod m 
      = ((a mod m)(b mod m) mod m)(c mod m) mod m  // Trim extra mod m 
      = (a mod m)(b mod m)(c mod m) mod m    // Reverse rule 1 with 
                  // a' = (a mod m)(b mod m) 
                  // b' = c mod m 

這爲實現三路模乘法提供了兩種選擇。最簡單的方法是將所有三個mod模項相乘，並對結果進行mod模擬，但如果對每個中間結果進行mod模擬，則不太可能發生溢出。假設C++：

template <typename T, size_t N> 
T mulmod(T (&multiplicands)[N], T m) { 
    T result = 1; 
    for (T n : multiplicands) 
     result = (result * (n % m)) % m; 
    return result; 
} 

int nums = {123, 345, 656, 841}; 
std::cout << mulmod(nums, 373) << "\n"; // Prints 88