最近发现扩展欧几里得的使用过程中有一些要注意的地方。
1.ax+by=c，这个式子中，如果b是负数，那么把它当作正数来算也无妨，因为只要给y乘一个(-1)就可以了。当然a也是同理。
2.如果解出来的x是一个负数，那么怎么变成正数呢？
方法如下：
得出来的解是ax+by=gcd(a,b)的解，令g=gcd(a,b)，那么两边同时乘以(c/g)可以得到(ac/g)*x+(b/g)*(y*c)=c。
先对ax+by=c考虑，我们可以转化成a(x+b)+b(y-a)=c。因此x可以是在原数字的基础上加减若干个b（即y前面的系数）。那么我们对上一行的x就可 以进行这样的操作，x=(x%mod+mod)%mod，其中mod等于y前面的系数，即b/g，这样mod小了，x才会成为最小的正整数。（虽然这里有点小疑问， 但是做了几题都可以用这样的方法那就这样子吧。。）
推荐题目是：POJ 2115和HDU 5114。
顺便，，扩展欧几里得的模板如下:
1 void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y) 2 { 3 if(!b) {d=a;x=1;y=0;} 4 else 5 { 6 ex_gcd(b,a%b,d,y,x); 7 y -= x*(a/b); 8 } 9 }