c++ 乘法逆元

采用扩展欧几里德算法
首先,欧几里德算法又称辗转相除法,用于求最大公约数,算法如下:
int Gcd(int a, int b)
{
if(b == 0)
return a;
return Gcd(b, a % b);
}
扩展欧几里德算法能计算a模b及b模a的乘法逆元,如下:
int gcd(int a， int b ， int&； ar，int &； br)

{

int x1，x2，x3；

int y1，y2，y3；

int t1，t2，t3；

if(0 == a)

{//有一个数为0，就不存在乘法逆元

ar = 0；

br = 0 ；

return b；

}

if(0 == b)

{

ar = 0；

br = 0 ；

return a；

}

x1 = 1；

x2 = 0；

x3 = a；

y1 = 0；

y2 = 1；

y3 = b；

int k；

for( t3 = x3 % y3 ； t3 ！= 0 ； t3 = x3 % y3)

{

k = x3 / y3；

t2 = x2 - k * y2；

t1 = x1 - k * y1；

x1 = y1；

x1 = y2；

x3 = y3；

y1 = t1；