拓展欧几里德

发表于

欧几里得

主要用于求解两个数的公约数

1
2
3
int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}

拓展欧几里得

扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int gcdEx(int a, int b, int *x, int *y)
{
    if(b==0){
        *x = 1,*y = 0;
        return a;
    }
    else{
        int r = gcdEx(b, a%b, x, y); 
        /* r = GCD(a, b) = GCD(b, a%b) */
        int t = *x;
        *x = *y;
        *y = t - a/b * *y;
        return r;
    }
}
1
2
3
4
5
6
7
int gcdEx(int a,int b,int &d,int &x,int &y){
    if(!b){d = a,x=1,y=0}
    else{
       gcdEx(b,a%b,d,y,x);
       y -= x*a/b;
    }
}

证明可参考
可以用来解不定方程

x0,y0 是一组特解，可以求得全部解

如果 gcd(a,b) mod c == 0 ,则该方程存在整数解，否则不存在整数解(可以应用到多维)