给定三个正数a、b和m。在模m下计算a/b。任务基本上是找到一个数字c，使（b*c）%m=a%m。 例如：
null
Input : a = 8, b = 4, m = 5Output : 2Input : a = 8, b = 3, m = 5Output : 1Note that (1*3)%5 is same as 8%5Input : a = 11, b = 4, m = 5Output : 4Note that (4*4)%5 is same as 11%5
以下文章是实现这一点的先决条件。 模乘逆 扩展欧几里德算法 我们能一直做模块划分吗？ 答案是“不”。首先，与普通算术一样，不定义0除。例如，不允许使用4/0。在模运算中，不仅4/0是不允许的，而且模6下的4/12也是不允许的。原因是，当模量为6时，12与0相等。 什么时候定义模块划分？ 当除数的模逆存在时，定义模除。整数“x”的倒数是另一个整数“y”，因此（x*y）%m=1，其中m是模。 什么时候存在反向？如前所述 在这里 ，如果“a”和“m”是同素数，则模“m”下存在一个逆数“a”，即它们的GCD为1。 如何找到模块划分？
The task is to compute a/b under modulo m.1) First check if inverse of b under modulo m exists or not. a) If inverse doesn't exists (GCD of b and m is not 1), print "Division not defined" b) Else return "(inverse * a) % m"
C
// C program to do modular division #include <stdio.h> // C function for extended Euclidean Algorithm int gcdExtended( int a, int b, int *x, int *y); // Function to find modulo inverse of b. It returns // -1 when inverse doesn't int modInverse( int b, int m) { int x, y; // used in extended GCD algorithm int g = gcdExtended(b, m, &x, &y); // Return -1 if b and m are not co-prime if (g != 1) return -1; // m is added to handle negative x return (x%m + m) % m; } // Function to compute a/b under modulo m void modDivide( int a, int b, int m) { a = a % m; int inv = modInverse(b, m); if (inv == -1) printf ( "Division not defined" ); else { int c = (inv * a) % m ; printf ( "Result of division is %d" , c) ; } } // C function for extended Euclidean Algorithm (used to // find modular inverse. int gcdExtended( int a, int b, int *x, int *y) { // Base Case if (a == 0) { *x = 0, *y = 1; return b; } int x1, y1; // To store results of recursive call int gcd = gcdExtended(b%a, a, &x1, &y1); // Update x and y using results of recursive // call *x = y1 - (b/a) * x1; *y = x1; return gcd; } // Driver Program int main() { int a = 8, b = 3, m = 5; modDivide(a, b, m); return 0; } |
Python3
# Python3 program to do modular division import math # Function to find modulo inverse of b. It returns # -1 when inverse doesn't # modInverse works for prime m def modInverse(b,m): g = math.gcd(b, m) if (g ! = 1 ): # print("Inverse doesn't exist") return - 1 else : # If b and m are relatively prime, # then modulo inverse is b^(m-2) mode m return pow (b, m - 2 , m) # Function to compute a/b under modulo m def modDivide(a,b,m): a = a % m inv = modInverse(b,m) if (inv = = - 1 ): print ( "Division not defined" ) else : print ( "Result of Division is " ,(inv * a) % m) # Driver Program a = 8 b = 3 m = 5 modDivide(a, b, m) # This code is Contributed by HarendraSingh22 |
PHP
<?php // PHP program to do modular division // Function to find modulo inverse of b. // It returns -1 when inverse doesn't function modInverse( $b , $m ) { $x = 0; $y = 0; // used in extended GCD algorithm $g = gcdExtended( $b , $m , $x , $y ); // Return -1 if b and m are not co-prime if ( $g != 1) return -1; // m is added to handle negative x return ( $x % $m + $m ) % $m ; } // Function to compute a/b under modulo m function modDivide( $a , $b , $m ) { $a = $a % $m ; $inv = modInverse( $b , $m ); if ( $inv == -1) echo "Division not defined" ; else echo "Result of division is " . ( $inv * $a ) % $m ; } // function for extended Euclidean Algorithm // (used to find modular inverse. function gcdExtended( $a , $b , & $x , & $y ) { // Base Case if ( $a == 0) { $x = 0; $y = 1; return $b ; } $x1 = 0; $y1 = 0; // To store results of recursive call $gcd = gcdExtended( $b % $a , $a , $x1 , $y1 ); // Update x and y using results of // recursive call $x = $y1 - (int)( $b / $a ) * $x1 ; $y = $x1 ; return $gcd ; } // Driver Code $a = 8; $b = 3; $m = 5; modDivide( $a , $b , $m ); // This code is contributed by mits ?> |
C++
// C++ program to do modular division #include<iostream> using namespace std; // C++ function for extended Euclidean Algorithm int gcdExtended( int a, int b, int *x, int *y); // Function to find modulo inverse of b. It returns // -1 when inverse doesn't int modInverse( int b, int m) { int x, y; // used in extended GCD algorithm int g = gcdExtended(b, m, &x, &y); // Return -1 if b and m are not co-prime if (g != 1) return -1; // m is added to handle negative x return (x%m + m) % m; } // Function to compute a/b under modulo m void modDivide( int a, int b, int m) { a = a % m; int inv = modInverse(b, m); if (inv == -1) cout << "Division not defined" ; else cout << "Result of division is " << (inv * a) % m; } // C function for extended Euclidean Algorithm (used to // find modular inverse. int gcdExtended( int a, int b, int *x, int *y) { // Base Case if (a == 0) { *x = 0, *y = 1; return b; } int x1, y1; // To store results of recursive call int gcd = gcdExtended(b%a, a, &x1, &y1); // Update x and y using results of recursive // call *x = y1 - (b/a) * x1; *y = x1; return gcd; } // Driver Program int main() { int a = 8, b = 3, m = 5; modDivide(a, b, m); return 0; } //this code is contributed by khushboogoyal499 |
输出：
Result of division is 1
模除不同于加法、减法和乘法。 一个区别是分裂并不总是存在（如上所述）。以下是另一个区别。
Below equations are valid(a * b) % m = ((a % m) * (b % m)) % m(a + b) % m = ((a % m) + (b % m)) % m// m is added to handle negative numbers(a - b + m) % m = ((a % m) - (b % m) + m) % m But, (a / b) % m may NOT be same as ((a % m)/(b % m)) % mFor example, a = 10, b = 5, m = 5. (a / b) % m is 2, but ((a % m) / (b % m)) % m is not defined.
参考资料： http://www.doc.ic.ac.uk/~mrh/330utor/ch03。html 本文由 德埃拉吉·古普塔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
