exgcd学习笔记

前言

今天膜你赛竟然要套$exgcd$

gcd

exgcd

形如$ax+by=c$的方程,当$gcd(a,b)|c$时,存在整数解$x,y$。
也就是说$exgcd$可以解$ax+by=gcd(a,b)$的方程。
令$a=b,b=a\mod b$,那么$bx+a\mod b\times y=gcd(b,a\mod b)$。
因为$gcd(a,b)=gcd(b,a\mod b)$。
所以$bx+a\mod b\times y=gcd(a,b)$。
又因为$a\mod b=a-b\times \lfloor {a/b} \rfloor$
所以$bx+(a-b\times \lfloor {a/b} \rfloor)\times y =gcd(a,b)$。
整理得:$a\times y+b\times (x-\lfloor {a/b} \rfloor)=gcd(a,b)$。
所以可以转化为$x_{new}=y,y_{new}=x-\lfloor {a/b} \rfloor$,继续求解即可。
当$b=0$时,$y=0,x=1,gcd=a$。

暂无评论

发送评论


				
上一篇
下一篇