acm|扩展欧几里德算法(附证明)

2022-01-07 数论 ACM

扩展欧几里德算法(附证明) tags : acm 数论

完全没接触过数论的渣渣脑抽不想敲代码,便看看数论冷静一下.

扩展欧几里德算法附证明
- 证明

扩展欧几里得算法在acm-icpc中是常用算法,主要用于在已知a,b的情况下求解一组x,y,使它们满足贝祖等式: ax+by=gcd(a,b)=d.
顾名思义,该算法是对欧几里得算法的拓展.其代码也是在gcd的基础上做小小的修改.

int exGcd(int a,int b,int &x,int &y) { if(b==0) { x=1; y=0; return a; } int r=exGcd(b,a%b,x,y); int t=x; x=y; y=t-a/b*y; return r; }

证明: 【acm|扩展欧几里德算法(附证明)】(证明过程参考自百度百科)
原式: ax+by=gcd(a,b)(假设a≥b)

当b=0时有gcd(a,b)=a,此时x=1,y=0
当b不为0时,根据欧几里得定理gcd(a,b)=gcd(b,amodb)可得ax+by=gcd(a,b)=gcd(b,amodb)=bx′+(amodb)y′,即

ax+by=bx′+(amodb)y′=bx′+(a?b??a/b?)y′
移项得
ax+by=bx′+(amodb)y′=ay′+b(x′??a/b?y′)
根据恒等定理,有
{x=y′y=x′??a/b?y′
这有什么用呢?x′和y′还是不知道呀.
重新来看看我们得到的两个等式.x和y是gcd(a,b)=ax+by的解,而x’和y’是在对gcd(a,b)按欧几里德算法进行一步后的结果对应的贝祖等式gcd(b,amodb)=bx′+(amodb)y′的解.也就是说,gcd(a,b)对应的贝祖等式的解x,y可以由gcd(b,amodb)对应等式的解x’,y’计算得出
由于欧几里德算法最后一步为gcd(d,0)=d,此时对应的等式的解为x=1,y=0,因此只要如上述代码,从gcd(d,0)往前处理,在进行欧几里德算法的递归的时候根据相邻两次调用间x,y和x’,y’的关系计算即可求出ax+by=gcd(a,b)的解.

更进一步,对于任意不定式ax′+by′=c,只需要在等式ax+by=gcd(a,b)=d两边乘上c/d即可得到解为x′=x?c/d,y′=y?c/d

如何得到所有解?
实际上在之前的计算和证明中我们得到的只是不定方程的一组解,那么怎样得到所有解呢?对于一般形式ax+by=c有通解x=p+kb,y=q?ka(k为任意整数).(证明略,只要代入一下就知道为什么通解是这个了)

推荐阅读

上一篇：Html页面清除缓存

下一篇：ObjectAnimator实现机制_源码分析