基本算法

对于不完全为 0 的非负整数 a，b 必然存在整数对 x，y ，使得 ax + by = gcd(a, b);

证明

  • 当b = 0 时：gcd(a, b) = a 此时易知x = 1,y = 0

  • 当b ≠ 0 时： 设ax0+by0=gcd(a,b)ax_0 + by_0 = \gcd(a,b)

由于gcd(a,b)=gcd(b,a%b)\gcd(a, b) = \gcd(b, a\% b)

我们如果设bx1+(a%b)y1=gcd(b,a%b)bx_1 + (a \% b)y_1 = \gcd(b, a\%b)

那么ax0+by0=bx1+(a%b)y1ax_0 + by_0 = bx_1 + (a \% b)y_1

即

展开移项得:ax0+by0=ay1+b(x1−⌊ab⌋y1)ax_0 + by_0 = ay_1 + b(x_1 - \lfloor {\frac{a}{b}}\rfloor y_1)

所以我们有： x0=y1 x_0 = y_1 y0=x1−⌊ab⌋y1 y_0 = x_1 - \lfloor {\frac{a}{b}}\rfloor y_1

于是我们在递归求gcd时回溯求x0x_0和y0y_0即可

Code

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define LL long long
using namespace std;
LL A, B;
inline LL Ex_gcd (LL A, LL B, LL &x, LL &y)
{
    if (!B)
    {
        x = 1;
        y = 0;
        return A;
    }
    LL Ans = Ex_gcd (B, A % B, x, y);
    LL tmp = x;
    x = y;
    y = tmp - (A / B)* y;
    return Ans;
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("Ex_gcd.in", "r", stdin);
    freopen("Ex_gcd.out", "w", stdout);
#endif
    scanf("%lld%lld", &A, &B);
    LL x, y;
    Ex_gcd(A, B, x, y);
    printf("%lld\n", (x + B) % B);
    return 0;
}