如何避免模乘中的溢出？-yiteyi-C++库

考虑下面 易于理解的 方法将两个数字相乘。

null

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 long                       
           
                         ll multiply(ll a, ll b, ll mod)                       
                         {                       
                                                 return                                     ((a % mod) * (b % mod)) % mod;                       
                         }                       

JAVA

                         // A Simple solution that causes overflow when                       
                         // value of (a % mod) * (b % mod) becomes more than                       
                         // maximum value of long int                       
           
           
                         static                                     long                                     multiply(                                     long                                     a,                                     long                                     b,                                     long                                     mod)                       
                         {                       
                                                 return                                     ((a % mod) * (b % mod)) % mod;                       
                         }                       
           
                         // This code contributed by gauravrajput1                       

Javascript

                         <script>                       
           
                         function                                     multiply(a,b,mod)                       
                         {                       
                                                 return                                     ((a % mod) * (b % mod)) % mod;                       
                         }                       
           
           
                         // This code is contributed by rag2127                       
                         </script>                       

当乘法不会导致溢出时，上述函数可以正常工作。但如果输入的数字是这样的，乘法的结果超过了最大限制。例如，当mod=10时，上述方法失败 ¹¹ ，a=9223372036854775807( 最大长整型 )b=9223372036854775807( 最大长整型 )。请注意，可能会有较小的值失败。可能还有更多较小值的示例。事实上，任何一组值的乘法都可能导致一个大于最大极限的值。 如何避免溢出？ 我们可以递归乘法来克服溢出的困难。要将a*b相乘，首先计算a*b/2，然后将其相加两次。对于计算a*b/2，计算a*b/4等等（类似于对数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) % mod        b) Multiply 'a' with 2           a = (a * 2) % mod        c) Divide 'b' by 2           b = b/2  4)  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#

                         // 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                       

输出：

84232501249

感谢乌特卡什·特里维迪提出上述解决方案。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章