本文概述
- C
- Python 3
- 的PHP
例子:
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
//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)。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。
推荐阅读
- 算法设计(修改链表的内容)
- 模幂(模运算中的幂)
- 算法设计(从1到n的模乘逆)
- 循环冗余校验和Modulo-2分区
- 算法题(模数10 ^ 9 + 7(1000000007))
- 自学一年C#(WPF),第二年自学Android。登录
- Android性能优化系列之渲染优化
- android studio 学习之一
- Android中使用findViewByMe提升组件查找效率