拓展欧几里得
2020.3.29 数据结构与算法 1188 3 分钟
ax+by=gcd(a,b)
ax+by=c
线性同余方程
我们先回忆一下朴素的欧几里得算法(辗转相除法)
$gcd(a,b)=gcd(b,a%b)$
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
而拓展欧几里得(exgcd)常用来求$ax+by=gcd(a,b)$的一组解.
设$x_1,y_1$满足原方程$ax_1+by_1=gcd(a,b)$
根据欧几里得算法不妨构造这样一个方程:
$x_2,y_2$满足$bx_2+(a;mod;b)y_2=gcd(b,a;mod;b)$
所以可得 $ax_1+by_1=b