文档介绍：,用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理:定理:gcd(a,b)=gcd(b,amodb)欧几里德算法就是根据这个原理来做的,其算法用C++语言描述为:voidswap(int&a,int&b){intc=aa=b;b=c;}intgcd(inta,intb){if(0==a){returnb;}if(0==b){returna;}if(a>b){swap(a,b);}intc;for(c=a%b;c>0 ;c=a%b){a=b;b=c;}returnb;}、p,如果存在整数b,满足abmodp=1,则说,b是a的模p乘法逆元。定理:a存在模p的乘法逆元的充要条件是gcd(a,p)=:#include<>intgcd(inta,intb,int&ar,int&br){intx1,x2,x3;inty1,y2,y3;intt1,t2,t3;intk;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;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;ret