OI

【数论】扩展欧几里得

还是要心平气和地对待数论（

0、欧几里得算法

即辗转相除法，可以求出两整数a,b的最大公约数（和最小公倍数），用gcd(a,b)表示.

递归实现如下：

1
2
3
4
5
int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}

gcd(a,b)具有以下性质：

gcd(a,b)=gcd(b,a)=gcd(-a,b)=gcd(abs(a),abs(b))

gcd(a,b)=gcd(b,a%b)

1、扩展欧几里得

扩展欧几里得即欧几里得算法的扩展：

gcd(a,0)=a

以及由此引申出的对二元一次不定方程整数解的求解算法.

求解：ax+by=gcd(a,b),(x,y∈Z)

（其中，有定理ax+by=gcd(a,b)解一定存在，且ax+by=c有解的充要条件为c=k*gcd(a,b),k∈Z）

设 a>b 当 b=0 时，gcd(a,b)=a,x=1,y=0;

a>b>0时 设
ax1+by1=gcd(a,b)……①

bx2+(a%b)y2=gcd(b,a%b)……②

由性质， ∵gcd(a,b)=gcd(b,a%b)

∴ax1+by1=bx2+(a%b)y2

=>ax1+by1=ay2+b(x2-[a/b]*y2)

由此，可以递归得到原方程的一组解：
{
x1=y2
y1=x2-[a/b]*y2
}
其中x1,y1由x2,y2得到，由b=0时的边界条件，即可回溯求解.

其代码实现如下：

1
2
3
4
5
6
7
8
9
int extend_euclid(int a,int b,int *x,int *y){
    if(b==0){*x=1;*y=0;return a;}
    int d=extend_euclid(b,a%b,x,y);
    int t;
    t=*x;
    *x=*y;
    *y=t-a/b*(*y);
    return d;
}

可以看到，扩展欧几里得的写法包涵了欧几里得算法的内容，即返回值为gcd(a,b)，同时，调用后实参x,y的值即为方程ax+by=gcd(a,b)的一组解.

当不需要返回gcd(a,b)时，形式还可以为：

1
2
3
4
5
6
7
void extend_euclid(int a,int b,int *x,int *y){
    if(b==0){*x=1;*y=0;return;}
    extend_euclid(b,a%b,x,y);
    int t=*x;
    *x=*y;
    *y=t-a/b*(*y);
}

2.不定方程的通解

在得到方程ax+by=gcd(a,b)的一组解x0,y0后，

方程ax+by=c(c mod gcd(a,b)=0)的一组解为：

x1=x0*(c/gcd(a,b)),

y1=y0*(c/gcd(a,b))

由此，不定方程ax+by=c的通解为：

x=x1+b/gcd(a,b)*k,

y=y1-a/gcd(a,b)*k(k∈Z)

以上即扩展欧几里得的内容，应用可参见：
青蛙的约会