浅谈扩展欧几里得

前置知识

朴素欧几里得

问题

已知 $a$ $,$ $b$ , 求一组$(x,y)$满足$ax+by=c$

定理

无解：$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倒置
}

答案记得乘c除以$\gcd(a, b)$

证明

易得 a $\mid$ $\gcd(a, b)$, b $\mid \gcd(a, b)$, c $\mid \gcd(a, b)$

故将a,b,c除以$\gcd(a, b)$得a',b',使a',b'互质

设x', y', a'x'+b'y'=1

则x=c'x',y=c'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)