浅谈扩展欧几里得
前置知识
朴素欧几里得
问题
已知 $a$ $,$ $b$ , 求一组$(x,y)$满足$ax+by=gcd(a,b)$
定理
无解：$c \mid \gcd(a, b)$不成立
有解
a,b中一个为负则对其加另一个直至其为正，两个为负则翻转正负（包括答案）
void ex_gcd(int a,int b,int &x,int &y){ if(!b) x=1,y=0; else ex_gcd(b, a % b, y, x),y-=a/b*x; //x,y倒置 }
证明
ax+by=$\gcd(a, b)$
$\Rrightarrow$ax+by=$\gcd(b,$a%b$)$
=bx+(a $\bmod b$)*y
=bx+(a-$\left \lfloor \frac{a}{b} \right \rfloor$b) y
=ay+b(x-$\left \lfloor \frac{a}{b} \right \rfloor$y)
故x变为y , y变为(x-$\left \lfloor \frac{a}{b} \right \rfloor$y)