今天膜你赛竟然要套exgcd
inline int gcd(int a,int b){
return !b?a:gcd(b,a%b);
}
形如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;
}
}