拓展欧几里得算法

__mt19937__ · 2025-02-20 21:20:15 · 算法·理论

拓展欧几里得算法

欧几里得算法

一般形式

证明

因为 gcd(a,b)=gcd(b,a-b)，所以可以简化减法运算为模运算。

即 gcd(a,b)=gcd(b,a \bmod b)。

code

inline int gcd (register const int x, register const int y)
{

  return y == 0 ? x : gcd (y, x % y);
}

主要步骤

拓展欧几里得算法主要用来求一个形如 ax + by = k 的不定方程的最小解。

然后我们就假设当前上一层的答案为x_1,y_1，则可得：

gcd(a,b) = ax + by gcd(b,a \bmod b) = bx_1 + (a\bmod b)y_1 ax + by = bx_1 + (a \bmod b)y_1

又因为 a \bmod b = a-\lfloor{a \over b}\rfloor b

所以 ax + by = bx_1 + ay_1 - b\lfloor {a \over b} \rfloor y_1

那么 x = y_1，y = x_1 - \lfloor {a \over b} \rfloor y_1

code

inline int Ex_Gcd (register const int a, register const int b, register int &x, register int &y)
{

    if (not b)
    {

        x = 1;
        y = 0;

        return a;
    }

    register const int d(Ex_Gcd (b, a % b, x, y));
    register const int temp (y);

    y = x - (a / b) * y;
    x = temp;

    return d;
}