假设y=am+bn;（a，b，m，n，y都是整数）。m和n是两个给定的整数，当a和b取适当的数时，y能取得到最小正整数。求最小正整数y以及满足这种情况的a，b。

Input
m，n

Output

y，a，b

Sample Input

7,9
Sample Output

1,4，-3

C语言求解~

y等于 m,n的最大公约数

然后式子两边同时除以y，变成关于裴蜀定理形式，可以套解法，也可以直接枚举

不懂。。。

看一下，和这个差不多的，http://，貌似是什么扩展欧几里德，8懂

你直接看数论里裴蜀定理的证明以及各种扩展就好了

http://zhidao.baidu.com/question/107995660.html?fr=qrl&cid=983&index=3
不妨设a,b都大于零，a>=b,用带余除法：
a=(x1)b+(r1),其中0=<（r1）<b
b=(x2)(r1)+(r2),其中0=<（r2）<(r1)
(r1)=(x3)(r2)+(r3),其中0=<（r3）<(r2)
.....到第n步，会有（这是因为数列rn单调递减到0）
(rn-3)=(xn-1)(rn-2)+(rn-1)
(rn-2)=(xn)(rn-1)+(rn)
(rn-1)=（xn+1)(rn)+0
容易证明a和b的最大公因数=b和r1的最大公因数=r1和r1的最大公因数=......=(rn)和0的最大公因数，所以（rn）=1,所以倒数第两个式子是
(rn-2)=(xn)(rn-1)+1
即1=(rn-2)-(xn)(rn-1)
由倒数第三个式子（rn-1）=(rn-3)-(xn-1)(rn-2)代入上式，得
1=[1+(xn)(xn-1)](rn-2)-(xn)(rn-3)
然后用同样的办法用它上面的等式逐个地消去(rn-2),...(r1),
得到1=ax+by。
这个是理论上求a,b的方法。

am+bn = gcd(m,n);
gcd(m,n) = gcd(n,m%n);
gcd(n,m%n) = cn+d(m%n);
cn + d(m%n) = gcd(m,n);
cn + d(m-n(m/n)) = gcd(m,n);
dm + cn-dn(m/n) = gcd(m,n);
dm + (c-d(m/n))n = gcd(m,n);

am+bn = gcd(m,n);
dm + (c-d(m/n))n = gcd(m,n);
对应相等得到a = d,b = c-d(m/n);
递归下去直到去求解am+b0 = gcd(m,0);此方程解为a = 1,b = 0;