参考链接：https://blog.csdn.net/qq_43553133/article/details/88931775

其实就是化了一个式子，作用就是求解 ax + by = gcd(a,b) x，y的值

 1 int exGcd(int a,int b,int &x,int &y)
 2 {
 3     if(b==0)
 4     {
 5         x = 1;
 6         y = 0;
 7         return a;
 8     }
 9     int r = exGcd(b,a%b,x,y);
10     t = x; x = y;
11     y = t-a/b*y;
12     return r;
13 }

View Code