标签:exgcd

1 篇文章

exgcd学习笔记
前言 今天膜你赛竟然要套$exgcd$ gcd [crayon-5db07146ebc39893796132/] 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\time…