扩展欧几德

扩展欧几德

a*x + b*y = n
求该二元一次方程的解
当且仅当  n % gcd(a,b) == 0

 所以方程 a*x+b*y=n；我们可以先用扩展欧几里德算法求出一组x0

，y0。也就是a*x0+b*y0=gcd（a，b）；然后两边同时除以gcd（a，b

），再乘以n。这样就得到了方程a*x0*n/gcd（a，b）+b*y0*n/gcd（

a，b）=n；我们也就找到了方程的一个解。

   若gcd（a，b）=1，且x0，y0为a*x+b*y=n的一组解，则该方程的

任一解可表示为：x=x0+b*t，y=y0-a*t；且对任一整数t，皆成立。

（这个证明比较简单，就不写了）

     这样我们就可以求出方程的所有解了，但实际问题中，我们往

往被要求去求最小整数解，所以我们就可以将一个特解x，t=b/gcd（

a，b），x=(x%t+t）%t；就可以了