「学习笔记」exgcd

发表于 更新于 分类于 阅读次数： 本文字数： 688 阅读时长 ≈ 1 分钟

扩展欧几里得算法(exgcd)

求解不定方程 ax+by=gcd(a,b)ax+by=gcd(a,b)

设

ax+by=gcd(a,b)ax+by=gcd(a,b)

bx′+(a%b)y′=gcd(b,a%b)bx'+(a\%b)y'=gcd(b,a\%b)

因为

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

其中

a%b=a−b⌊ab⌋a\%b=a-b\left\lfloor\dfrac{a}{b}\right\rfloor

所以

ax+by=bx′+(a%b)y′=bx′+(a−b⌊ab⌋)y′ax+by=bx'+(a\%b)y'=bx'+(a-b \left\lfloor\dfrac{a}{b}\right\rfloor)y'

整理可得

ax+by=ay′+b(x′−⌊ab⌋y′)ax+by=ay'+b(x'-\left\lfloor\dfrac{a}{b}\right\rfloor y')

所以

x=y′,y=x′−⌊ab⌋y′x=y',y=x'-\left\lfloor\dfrac{a}{b}\right\rfloor y'

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