如果事先不了解 欧几里得算法 ,请点击。
扩展欧几里得算法:对于不完全为0的非负整数 a,b,必然存在整数对 X,Y,使得 aX + bY = gcd(a,b)。
解法见注释。
/*
How to solve "aX + bY = gcd(a,b)" ?
1、if b=0,
gcd(a,b) = a,
X = 1 , Y is any number.
For convenience,we make Y equals 0.
2、if b!=0,
gcd(a,b) = aX1 + bY1;
gcd(b,a%b) = bX2 + (a%b)Y2;
----> (a-a/b*b)Y2;
--> aX1 + bY1 = aY2 + b(X2-a/b*Y2);
--> X1 = Y2 , Y1 = X2-a/b*Y2;
So w......
阅读全文