扩展欧几里得算法

由于早上刚学，理解不是很深刻，此篇博客仅供自己加深记忆用

作用

比较直观的就是在方程组$ax+by=gcd(a,b)$中求解整数解$x,y$。另外通过一系列的变换等作用很大。

代码实现

递归法求$x,y$：当b为0时，显然特解为$x=1,y=0$，在朴素欧几里得的递归写法中，最后肯定会递归到$b=0$，利用这一特点，我们在扩展欧几里得中递归到特解，然后回溯到$a,b$的解。

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); } 示例（朴素欧几里得递归写法） void exgcd(ll a, ll b, ll &x, ll &y) { if (!b) //递归到特解开始回溯 { x = 1; y = 0; return; } exgcd(b, a % b, x, y); //求得x2,y2 ll temp = x; x = y; //回溯，利用x2递推x1 y = temp - (a / b) * y; //回溯，利用y2递推y1 } int main() { ll a, b, x, y; cin >> a >> b; exgcd(a, b, x, y); cout << x << ' ' << y << endl; return 0; } 示例（扩展欧几里得递归写法） #### 参考资料 1. [扩展欧几里得算法](https://blog.csdn.net/u014634338/article/details/40210435) 2. [题解 P5656 【【模板】二元一次不定方程(exgcd)】](https://www.luogu.com.cn/blog/user22649/solution-p5656)