文章浏览阅读1.1w次，点赞13次，收藏18次。扩展欧几里德算法(附证明)扩展欧几里得算法在acm-icpc中是常用算法,主要用于在已知a,b的情况下求解一组x,y,使它们满足贝祖等式: ax+by=gcd(a,b)=dax+by = gcd(a, b) =d._扩展欧几里得算法证明...

文章浏览阅读297次。证明:由欧几里得算法知:gcd(a,b)=gcd(b,a%b).由裴蜀定理知:一定存在x1和y1满足a*x1+b*y1=gcd(a,b),且也一定存在b*x2+a%b*y2=gcd(b,a%b).因此由欧几里得算法和裴蜀定理知:gcd(a,b)=gcd(b,a%b).a*x1+b*y1=gcd(a,b).b*x2+a%b*y2=gcd(b,a%b).故:a*x1+......

关于欧几里得算法，贝祖等式，扩展欧几里得算法，Wikipedia的解释非常非常详细了。 另外，看了好多别人优秀的总结，我认为最详尽的就是ACM之家的总结。 这里自己再总结一次…实际上就是把别人总结的，我认为有助于自己......

文章浏览阅读3.2k次，点赞5次，收藏7次。欧几里得算法，也叫做辗转相除法，gcd(a, b) = gcd (b, a%b)，即a和b最大公约数等于b和a%b的最大公约数。相信大家都会用，但是很多人不知道为什么，我也看了很多文章，写的都不太相同，这......

文章浏览阅读9.9k次，点赞35次，收藏56次。关于欧几里得算法，贝祖等式，扩展欧几里得算法，Wikipedia的解释非常非常详细了。 另外，看了好多别人优秀的总结，我认为最详尽的就是ACM之家的总结。 这里自己再总结一次…实际......

文章浏览阅读297次。一.扩展欧几里得算法是求a*x+b*y=c的通解。二.若a*x+b*y=c有解，设t=gcd(a,b),则c%t=0。三.证明： 1.设a*x+b*y=t,当b=0时，t=a（为什么？因为gcd算法，if(b==0) return a;），则有a*x=a，易得x=1. 2.设a*x1+b*y1=gcd(a,b),b*x2+(a%b)*......

文章浏览阅读502次。裴蜀定理： 存在两个正整数a,b,使得a * x + b * y = gcd( a , b )证明方法（扩展欧几里得算法）： 1、当 b = 0 时 gac( a , b ) = a 易知 x = 1,y = 0,使得a * x + b * y = 0 2、当b != 0 时 gcd( a , b ) = gcd( b , a % b);---------------------......

文章浏览阅读538次。扩展欧几里得算法实际上就是对于ax+by=gcd(a,b)，一定有一组整数解x，y使其成立对于这个式子的证明，可以采用数学归纳法进行实现，先证明当n= 1时命题成立。假设n=m时命题成立，那么可以推导出在n=m+1时命......