分类 数学 下的文章

欧几里得算法

欧

欧氏算法用来求出$ A, B $二数的最大公约数，其实就是辗转相除法。
首先，下文标记的GCD = Greatest Common Divisor != CCP。
算法建立在一个显然的结论上：$$ GCD(A, B) = GCD(B, A \\, \mathbf{mod} \\, B) $$
即$$ GCD(A, B) | A \\, \mathbf{mod} \\, B $$
证明如下。
因为$ GCD(A, B) | A, B $，而$ A = \lfloor \frac{A}{B} \rfloor B + A \\, \mathbf{mod} \\, B $，等式左边整除$ GCD(A, B) $，加号左边也是，所以，加号右边整除$ GCD(A, B) $，即$ GCD(A, B) | A \\, \mathbf{mod} \\, B $。
以上咯。

template<class T>
T gcd(T a, T b)
{
    return b == 0 ? a : gcd(b, a % b);
}

拓欧

拓欧是来求解丢翻图方程$$ Ax+By=(A, B) $$
首先我们通过普通欧氏算法可以知道，算法必有一个终止态，即$ A_0 = (A, B), x_0=1, B_0=0, y_0=0 $。那我们将其视为特解，就得思考如何反推回原方程。
假设我们已经解出方程$ B_0x+(A_0 \\, \mathbf{mod} \\, B_0)y=(A, B) $的解，要反推回$ A_0x+B_0y=(A, B) $，则

$$ \begin{align} 记d &= (A, B) \\\\ 则d &= Bx_1 + (A \\, \mathbf{mod} \\, B)y_1 \\\\ &= Bx_1 + (A - \lfloor \frac{A}{B} \rfloor B)y_1 \\\\ &= Bx_1 + Ay_1 - \lfloor \frac{A}{B} \rfloor B y_1 \\\\ &= Ay_1 + B(x_1 - \lfloor \frac{a}{B} \rfloor y_1) \\\\ \end{align} $$

代码

template<class T>
void gcd(T a, T b, T& x, T& y, T& d)
{
    if(b == 0)
        d = a, x = 1, y = 0;
    else
        gcd(b, a % b, y, x, d), y -= x * (a / b);
}
  1. 1
  2. 2