exgcd学习笔记

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;
    }
}