扩展欧几里得算法 | exgcd 证明 + 板子 + 习题

扩展欧几里得算法 是在 欧几里得算法 && 裴楚定理 基础上得出来的

前提回顾：

欧几里得算法：
$gcd(a,b)=gcd(b,a\%b)$
裴楚定理：
若 a , b 是整数,且 gcd ⁡ ( a , b ) = d，那么对于任意的整数 x , y , ax + by 都一定是 d 的倍数，特别地，一定存在整数 x , y，使 ax + by = d 成立。

扩展欧几里得算法

当 $b=0$ 时 $ax+b=a$ 故： $x=1,y=0$
当 $b\ne 0$ 时
由欧几里得算法得： $gcd(a,b)=gcd(b,a\%b)$
由裴楚定理得：
$gcd(a,b)=ax+by$
$gcd(b,a\%b)=b{x}_1+(a\%b)y_1=b{x}_1+(a-\lfloor \frac{a}{b}\rfloor \times b)y_1=a{y}_1+b(x_1-\lfloor \frac{a}{b}\rfloor y_1)$
所以：
$x=y_1,y=x_1-\lfloor \frac{a}{b}\rfloor y_1$

可以用递归算法，先求出下一层的 $x_1,x_1$
再回代到上一层，层层回代，可以求出特解 $(x_0,y_0)$

构造通解
$x=x_0+\frac{b}{gcd(a,b)}\times k$
$y=y_0-\frac{a}{gcd(a,b)}\times k$
(考虑 $ax+by=0$ 构造)

exgcd板子代码

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

    // 或
    
    int d = exgcd(b, a % b, y, x);
    y = y - a / b * x;
    return d;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

例题一：

P1082 [NOIP2012 提高组] 同余方程
板子题，不做解释。

AC代码：

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

   // 或
   
   int d = exgcd(b, a % b, y, x);
   y = y - a / b * x;
   return d;
}
void solve()
{
   cin >> a >> b;
   int x, y;
   int d = exgcd(a, b, x, y);
   cout << (x % b + b) % b << '\n';
}
int main()
{
   buff;
   solve();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

例题二：

青蛙的约会

思路：

假设跳了 t 次后相遇，则可以列出方程：$(x+mt)\%L=(y+nt)\%L$，将未知数 t 移到等式左边，常数移到等式右边，得到模线性方程：$(m-n)t\%L=(y-x)\%L$
利用扩展欧几里德定理可以求得 t 的通解 $(t_0+kd|k为任意整数)$，由于这里需要求 t 的最小正整数，而 $t_0$ 不一定是最小的正整数，甚至有可能是负数，我们发现 $t$ 的通解是关于 d 同余的，所以最后的解可以做如下处理：$ans=(t_0\%d+d)\%d$

AC代码：

#define int long long
//#define ll long long
#define PII pair<int, int>
#define px first
#define py second
using namespace std;
const int mod = 1e9 + 7;
const int N = 100009;
int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    // int d = exgcd(b, a % b, x, y);
    // int t = x;
    // x = y, y = t - a / b * y;

    // 或
    
    int d = exgcd(b, a % b, y, x);
    y = y - a / b * x;
    return d;
}
void solve()
{
    int x, y, m, n, L;
    cin >> x >> y >> m >> n >> L;
    int a, b;
    int d = exgcd(n - m, L, a, b);
    if ((x - y) % d)
    {
        cout << "Impossible\n";
        return;
    }
    cout << ((a * ((x - y) / d)) % L + L) % L << '\n';
}
signed main()
{
    buff;
    solve();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43