算法设计（模划分详细实现）

本文概述

C
Python 3
的PHP

给定三个正数a, b和m。在模m下计算a/b。任务基本上是找到一个数字c, 使得(b * c)％m = a％m。
例子：

Input: a= 8, b = 4, m = 5 Output : 2Input: a= 8, b = 3, m = 5 Output : 1 Note that (1*3)%5 is same as 8%5Input: a= 11, b = 4, m = 5 Output : 4 Note 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++ 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 modlo 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() { inta= 8, b = 3, m = 5; modDivide(a, b, m); return 0; }

Python 3

# 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 modlo 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 ?>

输出如下：

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/330tutor/ch03.html
【算法设计（模划分详细实现）】本文作者：德莱拉吉·古普塔(Dheeraj Gupta)。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。