exgcd学习笔记
前言
今天膜你赛竟然要套exgcd
gcd
代码语言：javascript复制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=amod b，那么bx amod btimes y=gcd(b,amod b)。 因为gcd(a,b)=gcd(b,amod b)。 所以bx amod btimes y=gcd(a,b)。 又因为amod b=a-btimes lfloor {a/b} rfloor 所以bx (a-btimes lfloor {a/b} rfloor)times y =gcd(a,b)。 整理得：atimes y btimes (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。
代码语言：javascript复制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;
}
}
