【学习笔记】GCD & ExtendedGCD

$\text{GCD}$

普通的 $\gcd$ 算法相信我不用讲了吧（辗转相除法如果有问题的话应该不会来看我的 $\text{blog}$）。

$\text{ExtendedGCD}$

接下来是拓展的欧几里得算法。

拓展欧几里得算法是用来求已知 $(a, b)$ 时，求解一组 $(x, y)$ 使得 $ax + by = \gcd(a,b)$ 。

因为 $\gcd(a, b) = \gcd(b, a \bmod b) = \gcd(b, a - \left \lfloor \frac{a}{b} \right \rfloor b )$

所以 $ax + by = bx' + (a - \left \lfloor \frac{a}{b} \right \rfloor b)y'$

$$ax + by = ay' + b(x' - \left \lfloor \frac{a}{b} \right \rfloor y')$$

对比系数，可得$(x, y) = (y', x' - \left \lfloor \frac{a}{b} \right \rfloor y')$

由此，我们就可以将 $(a, b)$ 递归下去，转移到 $(b, a \bmod b)$ ，回溯时再将解也进行转移。

考虑到 $(a,b)$ 一定会转移到 $b=0$ 的情况，此时的 $(x, y) = (1, 0)$ ，再递归回去即可求出最终解

$\text{Code}$

本人习惯数学题写 $\text{int}$ ，然后在开头加上宏定义 $\text{define int long long}$ （$\text{LL}$, $\text{long long}$ 什么的真的太难写了）

//------------------- GCD ---------------------
int GCD(int a, int b) {
	return b == 0 ? a : GCD(b, a % b);
}

//--------------- Extended GCD -------------------

int ExtendedGCD(int a, int b, int& x, int& y) {
	if (a == 0 && b == 0) return -1;
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    int value = ExtendedGCD(b, a % b, y, x);
    y -= a / b * x;
    return value;
}