1 void gcd(LL a,LL b,LL &d,LL &x,LL &y) 2 { 3     if (!b) 4     { 5         x=1; 6         y=0; 7         d=a; 8     } 9     else10     {11         gcd(b,a%b,d,y,x); 12         y-=a/b*x;13     }14 }

为了便于理解，如果给出的a<0,一开始就把a=-a，c=-c，这样a，b，c都是正的了。

如果 （c%d！=0） 那么无解。

否则 令k=c/d， a‘=a/d ,   b‘=b/d;

对于函数求出的x，先映射一下 ，x*=k.

然后 x每次 加 b‘, y每次减 a‘ 是不会影响等式成立的。

这样 就可以 求出x的最小整数解。

     if (x<0)
        (x+=abs(x)/b‘ * b‘ + b‘) %= b‘;
     if (x>0)
        x-=x/b‘ * b‘;

拓展欧几里得算法