Skip to content

欧几里得&扩展欧几里得

朴素欧几里得

就是辗转相除法。\(\gcd(a,b)=\gcd(b,a\mod b)\) 

int gcd(int a, int b) {
    return !b ? a : gcd(b, a % b);
}
复杂度\(O(\log n)\)

扩展欧几里得

扩展欧几里得主要用来求解：

\(ax+by=\gcd(a,b)\)的特殊解。

可以用它求解这样的模线性方程：

\(ax \equiv b\pmod n\)

其实就是求\(ax+ny=b\)的解。

而这个方程有解的前提是\(b \mod \gcd(a,n)=0\),即\(b\)是\(\gcd(a,n)\)的倍数。这样才能转化为求\(ax+ny=\gcd(a,n)\)的一组解，在推到\(ax+ny=b\)上。

模板：

void exgcd(int a,int b,int &d,int &x,int &y){
    if(!b)d=a,x=1,y=0;
    else exgcd(b,a%b,d,y,x),y-=a/b*x;
}

这个递归的原理是：

假设当前\(ax+by=\gcd(b,a\mod b)\)有一组解\((x_1,y_1)\),则有：

\[\gcd(a,b)=\gcd(b,a \mod b)\\ ax+by=bx_1+(a-\lfloor\frac ab\rfloor b)y_1\\ ax+by=a(y_1)+b(x_1-\lfloor\frac ab\rfloor y_1) \]

因此\(x=y_1,y=x_1-\lfloor\frac ab\rfloor y_1\),这样迭代即可得出一组特殊解。

特别地，当\(b=0\)时，\(x=1,y=0\).

有了这组解，那么对于任意\(c\)满足\(ax+by=c,c \mod \gcd(a,b)=0\)的一组特殊解为\((\frac{x_0c}{\gcd(a,b)},\frac{y_0c}{\gcd(a,b)})\) (1)

那如果我想求任意一组可行解呢?

假设\(a'=a/ \gcd(a,b) ,b'=b/ \gcd(a,b)\)

那么对于一组\(ax+by=c\)的解\((x_1,y_1)\),有任意整数解\((x_1+kb',y_1-ka')\)(2)

这是因为对于任意一组解\((x_2,y_2)\),有：

\[ ax_1+by_1=ax_2+by_2\\ a(x_1-x_2)=b(y_2-y_1)\\ 设\gcd(a,b)=g,则\\ a'(x_1-x_2)=b'(y_2-y_1)\\ \because a'与b'互质\\ \therefore x_1-x_2=kb'\\ y_2-y_1=ka' \]

如果要求求出指定的解(如最小非负整数解)，根据要求向\(x_0\)加减\(b\)即可。

注意 (1) 和 (2) 顺序不能倒，因为先2后1相当于将\(b' \to \frac{b'c}{g}\),就不满足2的性质了。

复杂度同样为\(O(\log n)\)

P1082

模板题。

#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long 
using namespace std;
void exgcd(int a,int b,int &d,int &x,int &y){
    if(!b)d=a,x=1,y=0;
    else exgcd(b,a%b,d,y,x),y-=a/b*x;
}
int a,b,gcd,x,y;
signed main(){
    scanf("%lld%lld",&a,&b);
    exgcd(a,b,gcd,x,y);
    x=(x%b+b)%b;//注意，这里不用推导b'时因为题目规定gcd(a,b)=1,不是没有必要。
    printf("%lld",x);
    return 0;
}

P1516

化简题意后，我们知道原题要求的是一个最小非负整数解\(i\)，满足：

\[x+mi\equiv y+ni\pmod L\\ (m-n)i\equiv y-x\pmod L\\ 设a=m-n,b=L,c=y-x,则\\ ai+bj=c \]

到此，原题变为扩欧模板题。

#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long 
using namespace std;
void exgcd(int a,int b,int &d,int &x,int &y){
    if(!b)d=a,x=1,y=0;
    else exgcd(b,a%b,d,y,x),y-=a/b*x;
}
int x,y,n,m,L,a,b,c,g,i,j,_b,_a;
signed main(){
    scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&L);
    a=m-n,c=y-x,b=L;
    if(a<0 && b>0){
        while(a<0)a+=b;
    }else if(a>0 && b<0){
        while(b<0)b+=a;
    }else if(a<0 && b<0)a=-a,b=-b;//注意这里的负数处理方式。

    exgcd(a,b,g,i,j);
    _a=a/g,_b=b/g;
    if(c%g!=0){
        printf("Impossible");
        return 0;
    }
    i=(c/g)*i;
    i=(i%_b+_b)%_b;
    printf("%lld",i);
    return 0;
}