Si_Yue小屋
0%

贝祖定理

发表于 分类于

贝祖定理：\(xa+yb=(a,b)\)

a,b的最大公约数能被表示成\(a\)和\(b\)的线性组合

特别的，\((a,b)=1\)时，即\(a\)和\(b\)互素的时候，存在\(x\),\(y\)使得\(xa+yb=1\)

详情见：裴蜀定理 - OI Wiki (oi-wiki.org)

EXGCD问题

\(xa+yb=(a,b)\)的解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
LL exgcd(LL a,LL b,LL& x,LL& y){
    //递归法
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    LL d=exgcd(b,a%b,x,y);
    LL t=x;
    x=y;
    y=t-(a/b)*y;
    return d;
}

LL _exgcd(LL a,LL b,LL& x,LL& y){
    //迭代法
    x=1,y=0;
    int x1=0,y1=1,a1=a,b1=b;
    while(b1){
        LL q=a1/b1;
        tie(x,x1)=make_tuple(x1,x-q*x1);
        tie(y,y1)=make_tuple(y1,y-q*y1);
        tie(a1,b1)=make_tuple(b1,a1-q*b1);
    }
    return a1;
}

LL __exgcd(LL a,LL b,LL& x,LL& y){
    //矩阵法
    int x1=1,x2=0,x3=0,x4=1;
    while(b){
        LL c=a/b;
        tie(x1,x2,x3,x4,a,b)=make_tuple(x3,x4,x1-c*x3,x2-c*x4,b,a-c*b);
    }
    x=x1,y=x2;
    return a;
}