很精妙的算法，通过简单的递归，就能够求出一组解，满足ax+by = GCD(a,b);

这个等式是一个贝祖等式，贝祖定理(裴蜀定理).

code1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
int a, b, x, y；

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

int main() {
    scanf("%d %d", &a, &b);
    EXGCD(a,b,x,y);
    printf("%d %d", x, y);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
#define pir pair<int,int>    
int a, b, x, y;

pir EXGCD(int a,int b) {
    if (!b) return make_pair(1, 0);
    pir tmp = EXGCD(b, a%b);
    return make_pair(tmp.second ,tmp.first - a/b*tmp.second);
}

int main() {
    scanf("%d %d", &a, &b);
    pir ans = EXGCD(a,b);
    printf("%d %d",ans.first,ans.second);
    return 0;
}