定义gcd 是求最大公约数的算法求当时不定方程的一组整数解。分析欧几里得算法的核心是**递归**在最后一层得到一组解在回溯过程中求出原始解。我们需要计算递归下一层的参数值再推本层。由于的终止条件是此时的值是原式的最大公约数记作。不难看出在最后一层时(,) 时正好是的一组整数解。接着分析转移式从最底层推到第一层即可。转移式令当前层令下一层的参数分别为,,,则由于原式转化为假设我们已经求出下一层的解则乘法后由原式得由此从递归最后一层推至第一层即可求出的一组解。时间复杂度扩展欧几里得算法的时间复杂度与欧几里得算法gcd相同均为。C代码#includebits/stdc.h using namespace std; int a,b,x,y,d; void exgcd(int a,int b,int x,int y){//注意是引用传参 if(b0){ x 1,y 0; d a;//记录gcd(a,b) return ; } exgcd(b,a%b,x,y); int x_ x;//记录x x y; y x_-a/b*y; } int main(){ scanf(%d%d,a,b); exgcd(a,b,x,y); printf(%dx%dy %d\n,a,b,d); printf(x %d\ny %d,x,y); return 0; }void exgcd(int a,int b,int x,int y){ if(b0){ x 1,y 0; d a; return ; } exgcd(b,a%b,y,x);//返回后x,y交换 y - a/b*x;//原y换位xx换位y原式x-a/b*y,换后y-a/b*x }