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

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; }}

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

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

相关阅读
欧几里得定理公式【欧几里得定理公式】在几何之地冒险 解谜新作《欧几里得之地》上架

原本对于许多玩家来说,益智类游戏在他们眼中似乎都是比较幼稚的,他们更愿意去选择一些动作类或者射击类游戏。不过《纪念碑谷》的推出,让很多玩家对于这种游戏的看法有了比较大的改变,自从这款游戏推出并大获成功之后。

欧几里得几何原本【欧几里得几何原本】欧几里得和他的《几何原本》

尽管我们对古希腊数学家欧几里得了解不多,但我们知道他生活在希腊统治下埃及的亚历山大城,他因写了极具开创性的《几何原本》而闻名于世。欧几里得的《几何原本》无疑是有史以来最重要的数学著作之,一直到19世纪这本书都被认为是所有学者的基础读物。

欧几里得几何游戏【欧几里得几何游戏】欧几里得之地:不懂几何者不得入内

从几何知识到益智游戏的华丽转身,《欧几里得之地》尝试将晦涩的数学化为简单易懂的图形,像早些年的经典益智游戏《小3传奇》那样,用最简单的方式缩短大众与数学之间的距离。事实上,本作已经将删繁就简的功夫练到炉火纯青。

欧几里得游戏【欧几里得游戏】纪念碑谷相似的解谜游戏《欧几里得之地》限时6折促销

《欧几里得之地》(Euclidean Lands)是由kunabi brother GmbH推出的一款全新解谜游戏,该作不仅在美术和环境设置上与《纪念碑谷》谜之相似,而且还在玩法上借鉴了Square Enix的GO系列。

欧几里得角膜塑形镜【欧几里得角膜塑形镜】回望欧几里得几何 | 詹克明

“少年读诗如隙中窥月,中年读诗如庭中望月,老年读诗如台上观月”(张潮《幽梦影》)。读诗如此,读欧几里得几何学也同样如此。中学时代按照课本一点都不“走心”地读几何与耄耋之年再次捧读13卷的欧几里得《几何原本》。

推荐阅读
小学语文教学大纲模板【小学语文教学大纲模板】俄专家建议:俄罗斯学校需统一汉语教学大纲
小河淌水是哪里的民歌【小河淌水是哪里的民歌】世界名曲《小河淌水》是这样产生的……
唐子豪cba数据唐子豪cba数据 林书豪第二CBA体测不合格!唐子豪成篮坛最大伤仲永
东方国信公司怎么样【东方国信公司怎么样】东方国信(300166.SZ)拟改聘亚太(集团)为2019年度审计机构
于右任心经于右任心经 国民党元老于右任为何会为《新华日报》题写报名?
苗侨伟演反派都讨喜苗侨伟演反派都讨喜 钟澍佳监制《守护神》 苗侨伟黄宗泽主演