给定一个整数a，b，m。求（a*b）mod m，其中a，b可能很大，它们的直接乘法可能会导致溢出。但是，它们小于允许的最大long int值的一半。
null
例如：
Input: a = 426, b = 964, m = 235Output: 119Explanation: (426 * 964) % 235 = 410664 % 235 = 119Input: a = 10123465234878998, b = 65746311545646431 m = 10005412336548794 Output: 4652135769797794
A. 缺乏经验的 方法是使用任意精度的数据类型，例如 智力 用python或 大整数 用Java编写的类。但这种方法不会有什么成效，因为字符串到int的内部转换，然后执行操作，会导致二进制系统中加法和乘法的计算速度减慢。
高效的解决方案： 因为a和b可能是非常大的数字，如果我们试图直接相乘，那么它肯定会溢出。因此，我们使用乘法的基本方法。， a*b=a+a+…+a（b次） 所以我们可以很容易地计算加法的值（在模m下），而不需要任何计算 计算溢出。但如果我们试图增加 A. 反复达到 B 那么，对于b的大值，它肯定会超时，因为这种方法的时间复杂度将变成O（b）。
因此，我们将上述重复的步骤 A. 以更简单的方式，即：。，
If b is even then a * b = 2 * a * (b / 2), otherwise a * b = a + a * (b - 1)
以下是描述上述解释的方法：
C++
// C++ program of finding modulo multiplication #include<bits/stdc++.h> using namespace std; // Returns (a * b) % mod long long moduloMultiplication( long long a, long long b, long long mod) { long long res = 0; // Initialize result // Update a if it is more than // or equal to mod a %= mod; while (b) { // If b is odd, add a with result if (b & 1) res = (res + a) % mod; // Here we assume that doing 2*a // doesn't cause overflow a = (2 * a) % mod; b >>= 1; // b = b / 2 } return res; } // Driver program int main() { long long a = 426; long long b = 964; long long m = 235; cout << moduloMultiplication(a, b, m); return 0; } // This code is contributed // by Akanksha Rai |
C
// C program of finding modulo multiplication #include<stdio.h> // Returns (a * b) % mod long long moduloMultiplication( long long a, long long b, long long mod) { long long res = 0; // Initialize result // Update a if it is more than // or equal to mod a %= mod; while (b) { // If b is odd, add a with result if (b & 1) res = (res + a) % mod; // Here we assume that doing 2*a // doesn't cause overflow a = (2 * a) % mod; b >>= 1; // b = b / 2 } return res; } // Driver program int main() { long long a = 10123465234878998; long long b = 65746311545646431; long long m = 10005412336548794; printf ( "%lld" , moduloMultiplication(a, b, m)); return 0; } |
JAVA
// Java program of finding modulo multiplication class GFG { // Returns (a * b) % mod static long moduloMultiplication( long a, long b, long mod) { // Initialize result long res = 0 ; // Update a if it is more than // or equal to mod a %= mod; while (b > 0 ) { // If b is odd, add a with result if ((b & 1 ) > 0 ) { res = (res + a) % mod; } // Here we assume that doing 2*a // doesn't cause overflow a = ( 2 * a) % mod; b >>= 1 ; // b = b / 2 } return res; } // Driver code public static void main(String[] args) { long a = 10123465234878998L; long b = 65746311545646431L; long m = 10005412336548794L; System.out.print(moduloMultiplication(a, b, m)); } } // This code is contributed by Rajput-JI |
Python3
# Python 3 program of finding # modulo multiplication # Returns (a * b) % mod def moduloMultiplication(a, b, mod): res = 0 ; # Initialize result # Update a if it is more than # or equal to mod a = a % mod; while (b): # If b is odd, add a with result if (b & 1 ): res = (res + a) % mod; # Here we assume that doing 2*a # doesn't cause overflow a = ( 2 * a) % mod; b >> = 1 ; # b = b / 2 return res; # Driver Code a = 10123465234878998 ; b = 65746311545646431 ; m = 10005412336548794 ; print (moduloMultiplication(a, b, m)); # This code is contributed # by Shivi_Aggarwal |
C#
// C# program of finding modulo multiplication using System; class GFG { // Returns (a * b) % mod static long moduloMultiplication( long a, long b, long mod) { long res = 0; // Initialize result // Update a if it is more than // or equal to mod a %= mod; while (b > 0) { // If b is odd, add a with result if ((b & 1) > 0) res = (res + a) % mod; // Here we assume that doing 2*a // doesn't cause overflow a = (2 * a) % mod; b >>= 1; // b = b / 2 } return res; } // Driver code static void Main() { long a = 10123465234878998; long b = 65746311545646431; long m = 10005412336548794; Console.WriteLine(moduloMultiplication(a, b, m)); } } // This code is contributed // by chandan_jnu |
PHP
<?php //PHP program of finding // modulo multiplication // Returns (a * b) % mod function moduloMultiplication( $a , $b , $mod ) { $res = 0; // Initialize result // Update a if it is more than // or equal to mod $a %= $mod ; while ( $b ) { // If b is odd, // add a with result if ( $b & 1) $res = ( $res + $a ) % $mod ; // Here we assume that doing 2*a // doesn't cause overflow $a = (2 * $a ) % $mod ; $b >>= 1; // b = b / 2 } return $res ; } // Driver Code $a = 10123465234878998; $b = 65746311545646431; $m = 10005412336548794; echo moduloMultiplication( $a , $b , $m ); // This oce is contributed by ajit ?> |
Javascript
<script> // JavaScript program for the above approach // Returns (a * b) % mod function moduloMultiplication(a, b, mod) { // Initialize result let res = 0; // Update a if it is more than // or equal to mod a = (a % mod); while (b > 0) { // If b is odd, add a with result if ((b & 1) > 0) { res = (res + a) % mod; } // Here we assume that doing 2*a // doesn't cause overflow a = (2 * a) % mod; b = (b >> 1); // b = b / 2 } return res; } // Driver Code let a = 426; let b = 964; let m = 235; document.write(moduloMultiplication(a, b, m)); // This code is contributed by code_hunt </script> |
输出
4652135769797794
时间复杂性： O（日志b） 辅助空间： O（1）
注： 只有在以下情况下，上述方法才会起作用： 2*m 可以用标准数据类型表示，否则会导致溢出。
本文由 Shubham Bansal .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
