扩展欧几里得

纯粹的EXGCD，借机复习一波扩欧；

 1 void exgcd(ll a, ll b, ll &d, ll &x, ll &y) {
 2     if(!b){
 3         x = 1;
 4         y = 0;
 5         d = a;
 6     }
 7     else  {
 8         gcd(b, a%b, d, y, x);
 9         y -= x * (a /b);
10     }
11 }

求解ax+by = gcd的模板就在这里；

假如我们要求解最小正整数解就需要加点操作；

ax + by = gcd 的结果为x，y

那么讲结果*c/gcd才能得到ax + by = c 的解（形如6x+2y = 4的解由3x+y = 2的解*2）

关键是为什么我们要将b = b/gcd呢

我们假设x = x + k* b/gcd, y = y - k * a/gcd,（为什么y是-自行画图像）

带入原方程中

ax + a* k* b/gcd + by - b * k * a/gcd = ax + by = c

依然成立，这里面的b/gcd和a/gcd实际上是等式的最小系数，b能得到的解b/gcd也能得到，而且b转化为b/gcd所得到的结果依然是c，所以并无影响。因此：

1 if(c % gcd == 0) {
2         b = b/gcd;
3         x = x * c / gcd;
4         x = (x % b + b) % b;
5     }此即为最小正整数解