BYR Achieve · 镜像论坛

【讨论】扩展欧几里得算法

2018/4/3镜像同步0 回复

感觉很有意思[ema3]，求最大公约数g的同时，求出ax+by = g的整数解x，y 扩展欧几里德算法欧几里德辗转相除法的基本原理：gcd(a,b)=gcd(b,a%b) 所以： ax + by = g //g=gcd(a,b) ==> bx’ + (a%b)y’ = g ==> bx’ + (a-a/b*b)y’ = g ==> ay’ + b(x’-a/b*y’) = g ==> x=y’、y=x’-a/b*y’ //迭代式根据迭代式，可以在欧几里德辗转相除法求 a,b 的最大公约数时，同时计算 ax+by=g 的一个整数解！ int gcd(int a,int b) { if(b==0) returen a; int g=gcd(b,a%b); return g; } int exgcd(int a,int b,int &x,int &y) { if(b==0) { x=1; y=0; return a;} // g*1=g int xx,yy; int g=exgcd(b,a%b,xx,yy); x=yy; y=xx-(a/b)*yy; return g; }

订阅后，新回复会通过你的通知中心匿名送达。