如何避免模数乘法溢出（） _算法设计与分析

本文概述

C ++
Java
Python3
C#

【如何避免模数乘法溢出（）】考虑以下简单两个数相乘的方法。

// A Simple solution that causes overflow when // value of (a % mod) * (b % mod) becomes more than // maximum value of long long int #define ll long longll multiply(ll a, ll b, ll mod) { return ((a % mod) * (b % mod)) % mod; }

当乘法不会导致溢出时, 上述功能可以正常工作。但是, 如果输入数字的乘积结果大于最大限制。
例如, 当mod = 10时, 上述方法将失败11, a = 9223372036854775807(最大long long int)和b = 9223372036854775807(最大long long int)。请注意, 可能会有较小的值可能会失败。可以有更多的较小值的示例。实际上, 任何与之相乘可以导致大于最大值的值的集合。
如何避免溢出？
我们可以递归乘法来克服溢出的困难。要乘以a * b, 请先计算a * b / 2, 然后再相加两次。为了计算a * b / 2, 请计算a * b / 4, 依此类推(类似于
log n求幂算法
)。

// To compute (a * b) % modmultiply(a, b, mod)1)ll res = 0; // Initialize result2)a = a % mod.3)While (b > 0)a) If b is odd, then add 'a' to result.res = (res + a) % modb) Multiply 'a' with 2a = (a * 2) % modc) Divide 'b' by 2b = b/24)Return res

下面是实现。
C ++

// C++ program for modular multiplication without // any overflow #include< iostream> using namespace std; typedef long long int ll; // To compute (a * b) % mod ll mulmod(ll a, ll b, ll mod) { ll res = 0; // Initialize result a = a % mod; while (b > 0) { // If b is odd, add 'a' to result if (b % 2 == 1) res = (res + a) % mod; // Multiply 'a' with 2 a = (a * 2) % mod; // Divide b by 2 b /= 2; }// Return result return res % mod; }// Driver program int main() { ll a = 9223372036854775807, b = 9223372036854775807; cout < < mulmod(a, b, 100000000000); return 0; }

Java

// Java program for modular multiplication // without any overflow class GFG {// To compute (a * b) % mod static long mulmod( long a, long b, long mod) { long res = 0 ; // Initialize result a = a % mod; while (b > 0 ) { // If b is odd, add 'a' to result if (b % 2 == 1 ) { res = (res + a) % mod; }// Multiply 'a' with 2 a = (a * 2 ) % mod; // Divide b by 2 b /= 2 ; }// Return result return res % mod; }// Driver code public static void main(String[] args) {long a = 9223372036854775807L, b = 9223372036854775807L; System.out.println(mulmod(a, b, 100000000000L)); } } // This code is contributed by Rajput-JI

Python3

# Python3 program for modular multiplication # without any overflow# To compute (a * b) % mod def mulmod(a, b, mod):res = 0 ; # Initialize result a = a % mod; while (b > 0 ):# If b is odd, add 'a' to result if (b % 2 = = 1 ): res = (res + a) % mod; # Multiply 'a' with 2 a = (a * 2 ) % mod; # Divide b by 2 b / / = 2 ; # Return result return res % mod; # Driver Code a = 9223372036854775807 ; b = 9223372036854775807 ; print (mulmod(a, b, 100000000000 )); # This code is contributed by mits

// C# program for modular multiplication // without any overflow using System; class GFG { // To compute (a * b) % mod static long mulmod( long a, long b, long mod) { long res = 0; // Initialize result a = a % mod; while (b > 0) { // If b is odd, add 'a' to result if (b % 2 == 1) { res = (res + a) % mod; } // Multiply 'a' with 2 a = (a * 2) % mod; // Divide b by 2 b /= 2; } // Return result return res % mod; } // Driver code public static void Main(String[] args) { long a = 9223372036854775807L, b = 9223372036854775807L; Console.WriteLine(mulmod(a, b, 100000000000L)); } } // This code is contributed by 29AjayKumar

输出如下：