扩展欧几里得
发表于 2018-08-31 |更新于 2018-08-31 |基础数论实现
扩展欧几里得是用来在 已知 $a, b$ 求解一组 $x, y$,使它们满足贝祖等式:$ax+by=gcd\left(a,b\right)$(解一定存在,根据数论中的相关定理).扩展欧几里得常用在求解模线性方程及方程组中.
贝祖定理:设 $a,b$ 是不全为零的整数,则存在整数 $x,y$,使得 $ax+by=gcd\left(a,b\right)$.
int exgcd(int a, int b, int &x, int &y)
if (b == 0)
x = 1, y = 0;
int q = exgcd(b, a % b