exgcd

定义

gcd 是求最大公约数的算法，求当时，不定方程的一组整数解。

分析

欧几里得算法的核心是**递归**，在最后一层得到一组解，在回溯过程中求出原始解。

我们需要计算递归下一层的参数值，再推本层。

由于的终止条件是，此时的值是原式的最大公约数，记作。

不难看出，在最后一层时，(,) 时正好是的一组整数解。

接着分析转移式，从最底层推到第一层即可。

转移式

令，

当前层

令下一层的参数分别为,,,，则

由于，原式转化为

假设我们已经求出下一层的解，则


乘法后


由原式

得



由此从递归最后一层推至第一层即可求出的一组解。

时间复杂度

扩展欧几里得算法的时间复杂度与欧几里得算法（gcd）相同，均为。

C++代码

#include<bits/stdc++.h> using namespace std; int a,b,x,y,d; void exgcd(int a,int b,int &x,int &y){//注意是引用传参 if(b==0){ 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(b==0){ x = 1,y = 0; d = a; return ; } exgcd(b,a%b,y,x);//返回后x,y交换 y -= a/b*x;//原y换位x，x换位y，原式x-a/b*y,换后y-a/b*x }