算法设计------扩展欧几里德算法

发表于 | 分类于

扩展欧几里德算法

定义： 扩展欧几里德算法，是欧几里德算法的扩展。已知整数a、b，扩展欧几里德算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足贝祖等式: 

ax + by = gcd(a,b).

有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数——这是众所周知的。然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
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);
        int t = *x;
        *x = *y;
        *y = t - a/b * *y;
        return r;
    }
}

时间复杂度

O(㏒ a + b)

如果对你有帮助的话，Star✨下一吧！