Exgcd

数论

---

//下面假设$a,b$都是非负整数

我们想求得一组$x,y$使得

$$\gcd(a,b) = ax+by$$

根据

$$b\neq 0 \implies \gcd(a,b) = \gcd(b,a\bmod b)$$

如果我们现在有$x',y'$使得

$$bx'+(a\bmod b)y' = \gcd(b,a\bmod b)$$

那么我们可以钦定

$$ax+by = bx'+(a\bmod b)y'$$

注意到

$$a\bmod b = a-\lfloor\frac a b\rfloor b$$
其中$\lfloor x\rfloor$表示小于等于$x$的最大整数。

所以

$$ax+by = bx'+( a-\lfloor\frac a b\rfloor b)y'$$

注：我们注意到这个方程里面有$2$个未知数却只有$1$个方程，那么根据线性代数相关知识我们可以知道这东西是有无数组解的。
注意到这个等式每一项只与a或b有关，所以我们只需要按照a和b分类一下这个东西就可以获得一组特解

魔改开始！

$$a(x)+b(y) = a(y')+b(x'-\lfloor\frac a b\rfloor y')$$

魔改结束！

看这个东西长得这么漂亮，这么对称，显然我们可以得到一组特解

$$x = y',y = x' - \lfloor\frac a b\rfloor y'$$

聪明的你一定发现了这个东西是个递归的式子，那么我们肯定要找到那组base case（也就是递归基）. 聪明的你也一定发现了这里的递归基就是当$b = 0$时

当$b = 0$时我们想求$x,y$使得$ax+by = \gcd(a,b)$的话，显然$x = 1,y = 0$就可以啦，大功告成。

附一下代码：

pair<int,int> exgcd(int a,int b){
    if(b == 0)return make_pair(1,0);
    pair<int,int>temp = exgcd(b,a%b);
    pair<int,int>ans = make_pair(temp.second,temp.first-a/b*temp.second);
    return ans;
}