扩展欧几里得算法（求乘法逆元）

2019-04-14 16:15发布

站内文章 / 模拟电子
10375 0 930
eg：求5关于模14的乘法逆元 15 = 5*2+1 5 = 4*1+1 说明5与14互素，存在5关于14的乘法逆元 1 = 5-4 = 5-（14-5*2）= 5*3-14 因此5关于模14的乘法逆元为3  a存在模b的乘法逆元的充要条件是gcd（a,b）= 1 互质：两个数的最大公约数为1，则称这两个数互质，也叫互素 对于扩展欧几里得算法求乘法逆元的步骤解析。 设a>b 显然当b=0,gcd(a,b)=a. 此时x=1，y=0 当b!=0时 设a*x1+b*y1 = gcd(a,b) b*x2+(a mod b)*y2 = gcd(b,a mod b) 因为 gcd(a,b) = gcd(b,a mod b) 所以 a*x1+b*y1 = b*x2+(a mod b)*y2 继续写就是 a*x1+b*y1 = b*x2+(a-(a/b)*b)*y2 = a*y2+b*x2-(a/b)*b*y2 代码模板 int kzojld(int a,int b,int &x,int &y) { if(b==0) { x=1; y=0; return a; } int r=kzojld(b,a%b,x,y); int t=x; x=y; y=t-a/b*y; return r; }  

热门文章