转：
http://www.mscenter.edu.cn/blog/jeffrey/articles/5994.htmlhttp://hi.baidu.com/xknuth/blog/item/491bf9198e26227adab4bded.htmlhttp://www.faq-it.org/archives/structure/0f0aeab192b1e0bdbd84d19d4ab80a28.php有等式ax+by=c,已知a、b、c,求x和y。 (a、b、c、x、y都是整数)
uml_practice ---------------------------------------------------------------
解不定方程ax + by = n的步骤如下:
(1)计算gcd(a, b). 若gcd(a, b)不能整除n，则方程无整数解；否则，在方程的两边同除以gcd(a, b)，得到新的不定方程a'x + b'y = n'，此时gcd(a', b') = 1
(2)求出不定方程a'x + b'y = 1的一组整数解x0, y0，则n'x0，n'y0是方程a'x + b'y = n'的一组整数解。
(3)根据&@^%W#&定理，可得方程a'x + b'y = n'的所有整数解为：
x = n'x0 + b't
y = n'y0 - a't
(t为整数)
这也就是方程ax + by = n的所有整数解
利用扩展的欧几里德算法，计算(a, b)和满足d = (a, b) = ax0 + by0的x0和y0，也就是求出了满足a'x0 + b'y0 = 1的一组整数解。因此可得：
x = n/d * x0 + b/d * t
y = n/d * y0 - a/d * t
(t是整数)