【数学】拓展欧几里得算法

拓展欧几里得算法

用于求解不定方程

定理

方程

ax+by=\gcd(a,b)

总有整数解

推广

对于更一般的方程

ax+by=c

有解当且仅当$gcd(a,b)|c$,则先求$=\gcd$的解,然后乘上$\frac{c}{\gcd(a,b)}$

代码

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