【欧几里得定律】扩展欧几里得定理详解和运用(就不信你看不懂!)

2020-04-15 - 欧几里得

扩展欧几里德算法是用来在已知a, b求解一组x,y使得ax by =c.(若 c%gcd(a,b)!=0)则无解 所以 我们求ax by=c是不是可以转化为求 ax by=kgcd(a,b) k为整数呢? ex1: 最大公因数的这个公式大家都认识吧? gcd(a,b)=gcd(b,a%b); 所以我们看:(用b代替a,a%b代替b) ax by=kgcd(a,b); bx (a%b)y=gcd(b,a%b)k=gcd(a,b)k; 故 ax by=bx (a%b)y; 又因为:a%b=a-a/bb; 故 ax by=bx (a%b)y=bx (a-a/b*b)*y; 看懂了没 ? 没懂 冷静分析 go to ex1 故我们解得 由此我们成功得到递归式以及边界条件,可以求解方程了,每次只需要递归exgcd(b,a mod b,x,y) ,然后处理一下即可得到方程ax by= gcd(a,b)的一组解。

【欧几里得定律】扩展欧几里得定理详解和运用(就不信你看不懂!)
【欧几里得定律】扩展欧几里得定理详解和运用(就不信你看不懂!)

对于求解方程ax by= c(gcd(a,b)

c),只需求解出方程ax by= gcd(a,b) 的一组解,将x, y分别乘上k即可得到ax by= c(gcd(a,b)

c)的一组解。(k=c/gcd(a,b)) 至此 ,扩展欧几里得定理便解决了。 接下来我们讲运用: 1:求解模线性方程

这是扩展欧几里得最常用的用法,比如求 ax ≡ 1 (mod b)的最小正整数解; (这里有人可能要问了,这和ax by=c有啥关系?) 首先,题目保证了gcd(a,b)一定是1(不然无解) 我们设r=ax%b, 有ax=bk r 然后ax ≡ 1 (mod b)就转换为了ax-bk=1 然后我们再设 y=-k,方程就转换成了 ax by=1 即ax b*y = gcd(a,b) = 1 就是妥妥的扩展欧几里得算法嘛!

【欧几里得定律】扩展欧几里得定理详解和运用(就不信你看不懂!)
【欧几里得定律】扩展欧几里得定理详解和运用(就不信你看不懂!)

!! 递归求x的值就好啦!!!! 这里我还要提一下:(取模的时候可能出现负数,记得取模的时候 mod然后%mod)

void exgcd(long long a,long long b){ if(b==0) //当b=0时就是遇到了特解,可以递归回去算答案了 { x=1,y=0; return ; } exgcd(b,a%b); long long k; k=x; x=y; y=k-(a/b)*y;}

2:乘法逆元

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 nk; for(t3=x3%y3;t3!

=0;t3=x3%y3) { k=x3/y3; t2=x2-k*y2;t1=x1-k*y1; x1=y1;x2=y2;x3=y3; y1=t1;y2=t2;y3=t3; } if(y3==1)//有乘法逆元 { ar=(y2 b)%b;//对求出来负的乘法逆元进行处理,使之在模b的完全剩余集里 br=(y1 a)%a;//原来这里是错的 return 1; } else//公约数不为1,无乘法逆元 { ar=0; br=0; return y3; }}

【欧几里得定律】扩展欧几里得定理详解和运用(就不信你看不懂!)
【欧几里得定律】扩展欧几里得定理详解和运用(就不信你看不懂!)

不定期更新 ,有什么疑惑欢迎评论,谢谢阅读!

相关阅读