欧几里得算法以及拓展欧几里得算法模板

欧几里得算法（辗转相除术）
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；

y2 = t2；

y3 = t3；

}

if( y3 == 1)

{

//有乘法逆元

ar = y2；

br = x1；

return 1；

}else{

//公约数不为1，无乘法逆元

ar = 0；

br = 0；

return y3；

}

}