计算（a*b）%c，使（a%c）*（b%c）可以超出范围-yiteyi-C++库

给定三个数字a、b和c，这样a、b和c最多可以是10 ¹⁶ .任务是计算（a*b）%c 一个简单的解决方案（（A%c）*（b%c））%c在这里不起作用。这里的问题是a和b可能很大，所以当我们计算（a%c）*（b%c）时，它超出了long int可以容纳的范围，因此发生溢出。例如，如果a=（10 ¹² +7），b=（10） ¹³ +5），c=（10 ¹⁵ +3). 现在长整型可以容纳4 x 10 ¹⁸ （大约）a*b比这个大很多。

null

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

我们可以求a+a+，而不是直接乘法………。（b次）并在每次添加a时取c的模量，这样就不会发生溢出。但考虑到a、b和c的约束条件，这将是低效的。我们必须以某种方式进行计算(∑ a） %c以优化的方式。我们可以用“分而治之”来计算它。主要思想是：

如果b是偶数，那么a*b=（2*a）*（b/2）
如果b是奇数，那么a*b=a+（2*a）*（（b-1）/2）

以下是算法的实现：

C++

                         // C++ program to Compute (a*b)%c                       
                         // such that (a%c) * (b%c) can be                       
                         // beyond range                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
                         typedef                                     long                                     long                                     int                                     ll;                       
           
                         // returns (a*b)%c                       
                         ll mulmod(ll a,ll b,ll c)                       
                         {                       
                                                 // base case if b==0, return 0                       
                                                 if                                     (b==0)                       
                                                 return                                     0;                       
           
                                                 // Divide the problem into 2 parts                       
                                                 ll s = mulmod(a, b/2, c);                       
           
                                                 // If b is odd, return                       
                                                 // (a+(2*a)*((b-1)/2))%c                       
                                                 if                                     (b%2==1)                       
                                                 return                                     (a%c+2*(s%c)) % c;                       
           
                                                 // If b is odd, return                       
                                                 // ((2*a)*(b/2))%c                       
                                                 else                       
                                                 return                                     (2*(s%c)) % c;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 ll a = 1000000000007, b = 10000000000005;                       
                                                 ll c = 1000000000000003;                       
                                                 printf                                     (                                     "%lldn"                                     , mulmod(a, b, c));                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to Compute (a*b)%c                       
                         // such that (a%c) * (b%c) can be                       
                         // beyond range                       
                         // returns (a*b)%c                       
                         class                                     GFG {                       
           
                                                 static                                     long                                     mulmod(                                     long                                     a,                                     long                                     b,                                     long                                     c) {                       
                                                 // base case if b==0, return 0                       
                                                 if                                     (b ==                                     0                                     ) {                       
                                                 return                                     0                                     ;                       
                                                 }                       
           
                                                 // Divide the problem into 2 parts                       
                                                 long                                     s = mulmod(a, b /                                     2                                     , c);                       
           
                                                 // If b is odd, return                       
                                                 // (a+(2*a)*((b-1)/2))%c                       
                                                 if                                     (b %                                     2                                     ==                                     1                                     ) {                       
                                                 return                                     (a % c +                                     2                                     * (s % c)) % c;                       
                                                 }                                     // If b is odd, return                       
                                                 // ((2*a)*(b/2))%c                       
                                                 else                                     {                       
                                                 return                                     (                                     2                                     * (s % c)) % c;                       
                                                 }                       
                                                 }                       
           
                         // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args) {                       
                                                 long                                     a = 1000000000007L, b = 10000000000005L;                       
                                                 long                                     c = 1000000000000003L;                       
                                                 System.out.println((mulmod(a, b, c)));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by PrinciRaj1992                       

Python3

                         # Python3 program of above approach                       
           
                         # returns (a*b)%c                       
                         def                                     mulmod(a, b, c):                       
           
                                                 # base case if b==0, return 0                       
                                                 if                                     (b                                     =                                     =                                     0                                     ):                       
                                                 return                                     0                       
           
                                                 # Divide the problem into 2 parts                       
                                                 s                                     =                                     mulmod(a, b                                     /                                     /                                     2                                     , c)                       
           
                                                 # If b is odd, return                       
                                                 # (a+(2*a)*((b-1)/2))%c                       
                                                 if                                     (b                                     %                                     2                                     =                                     =                                     1                                     ):                       
                                                 return                                     (a                                     %                                     c                                     +                                     2                                     *                                     (s                                     %                                     c))                                     %                                     c                       
           
                                                 # If b is odd, return                       
                                                 # ((2*a)*(b/2))%c                       
                                                 else                                     :                       
                                                 return                                     (                                     2                                     *                                     (s                                     %                                     c))                                     %                                     c                       
           
                         # Driver code                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                                 a                                     =                                     1000000000007                       
                                                 b                                     =                                     10000000000005                       
                                                 c                                     =                                     1000000000000003                       
                                                 print                                     (mulmod(a, b, c))                       
           
                         # This code is contributed by                       
                         # Sanjit_Prasad                       

C#

                         // C# program to Compute (a*b)%c                       
                         // such that (a%c) * (b%c) can be                       
                         // beyond range                       
                         using                                     System;                       
           
                         // returns (a*b)%c                       
                         class                                     GFG                       
                         {                       
                         static                                     long                                     mulmod(                                     long                                     a,                                     long                                     b,                                     long                                     c)                       
                         {                       
                                                 // base case if b==0, return 0                       
                                                 if                                     (b == 0)                       
                                                 return                                     0;                       
           
                                                 // Divide the problem into 2 parts                       
                                                 long                                     s = mulmod(a, b / 2, c);                       
           
                                                 // If b is odd, return                       
                                                 // (a+(2*a)*((b-1)/2))%c                       
                                                 if                                     (b % 2 == 1)                       
                                                 return                                     (a % c + 2 * (s % c)) % c;                       
           
                                                 // If b is odd, return                       
                                                 // ((2*a)*(b/2))%c                       
                                                 else                       
                                                 return                                     (2 * (s % c)) % c;                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     Main()                       
                         {                       
                                                 long                                     a = 1000000000007, b = 10000000000005;                       
                                                 long                                     c = 1000000000000003;                       
                                                 Console.WriteLine(mulmod(a, b, c));                       
                         }                       
                         }                       
           
                         // This code is contributed by mits                       

PHP

                         <?php                       
                         // PHP program to Compute (a*b)%c                       
                         // such that (a%c) * (b%c) can be                       
                         // beyond range                       
           
                         // returns (a*b)%c                       
                         function                                     mulmod(                                     $a                                     ,                                     $b                                     ,                                     $c                                     )                       
                         {                       
                                   
                                                 // base case if b==0, return 0                       
                                                 if                                     (                                     $b                                     ==0)                       
                                                 return                                     0;                       
           
                                                 // Divide the problem into 2 parts                       
                                                 $s                                     = mulmod(                                     $a                                     ,                                     $b                                     /2,                                     $c                                     );                       
           
                                                 // If b is odd, return                       
                                                 // (a+(2*a)*((b-1)/2))%c                       
                                                 if                                     (                                     $b                                     % 2 == 1)                       
                                                 return                                     (                                     $a                                     %                                     $c                                     + 2 *                       
                                                 (                                     $s                                     %                                     $c                                     ))  %                                     $c                                     ;                       
           
                                                 // If b is odd, return                       
                                                 // ((2*a)*(b/2))%c                       
                                                 else                       
                                                 return                                     (2 * (                                     $s                                     %                                     $c                                     )) %                                     $c                                     ;                       
                         }                       
           
                                                 // Driver Code                       
                                                 $a                                     = 1000000000007;                       
                                                 $b                                     = 10000000000005;                       
                                                 $c                                     = 1000000000000003;                       
                                                 echo                                     mulmod(                                     $a                                     ,                                     $b                                     ,                                     $c                                     );                       
                                   
                         // This code is contributed by anuj_67.                       
                         ?>                       

Javascript

                         <script>                       
           
                         // javascript program to Compute (a*b)%c                       
                         // such that (a%c) * (b%c) can be                       
                         // beyond range                       
                         // returns (a*b)%c                       
                         function                                     mulmod(a , b , c) {                       
           
                                                 // base case if b==0, return 0                       
                                                 if                                     (b == 0) {                       
                                                 return                                     0;                       
                                                 }                       
           
                                                 // Divide the problem into 2 parts                       
                                                 var                                     s = mulmod(a, parseInt(b / 2), c);                       
           
                                                 // If b is odd, return                       
                                                 // (a+(2*a)*((b-1)/2))%c                       
                                                 if                                     (b % 2 == 1) {                       
                                                 return                                     (a % c + 2 * (s % c)) % c;                       
                                                 }                       
                                                 // If b is odd, return                       
                                                 // ((2*a)*(b/2))%c                       
                                                 else                                     {                       
                                                 return                                     (2 * (s % c)) % c;                       
                                                 }                       
                                                 }                       
           
                         // Driver code                       
                         var                                     a = 1000000000007, b = 10000000000005;                       
                         var                                     c = 1000000000000003;                       
                         document.write((mulmod(a, b, c)));                       
           
                         // This code contributed by Princi Singh                       
           
                         </script>                       

输出：

74970000000035

看见这用于样本运行。 时间复杂性： O（日志b）本文由 马杜尔·莫迪 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以写一篇文章，然后将文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论

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

THE END

技术文章