exgcd学习笔记

前言

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

gcd

inline int gcd(int a,int b){
    return !b?a:gcd(b,a%b);
}

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$。

inline void exgcd(int a,int b,int &x,int &y,int &gcd){
    if(!b) gcd=a,y=0,x=1;
    else{
        gcd(b,a%b,x,y,gcd);
        int tmp=x;x=y;y=tmp-(a/b)*y;
    }
}