最大公因数（欧几里得算法）

$gcd(a,b)=gcd(b\%a,a)$（不一定需要a<b）

$gcd(0,b)=b$

1 inline int gcd(int a,int b){2     return a==0?b:gcd(b%a,a);3 }

扩展欧几里得

寻找$ax+by=gcd(a,b)$的一组解x,y（一定存在整数解）

$ax+by=gcd(a,b)=gcd(b\%a,a)=(b-\lfloor\frac{b}{a}\rfloor*a)x'+ay'$

所以有一组解$x=y'-\lfloor\frac{b}{a}\rfloor*x',y=x'$

用此法可解同余方程$ax=b(\mod c)$，只要把$ax+cy=b$两边同除$b/gcd(a,c)$即可，所以有解的条件是$gcd(a,c)|b$

1 inline ll exgcd(ll a,ll b,ll &x,ll &y){2     if(!a){3         y=1;return b;4     }else{5         ll t=exgcd(b%a,a,x,y);6         y-=(b/a)*x;swap(x,y);7         return t;8     }9 }