1、扩展欧几里得
扩欧，扩展gcd，同余方程，二元一次方程、不定方程(exgcd)
一般形式：
\[ax+by=c
\]
\[ax=c\pmod{b}
\]
上下两个方程可互相转化
考虑对于
\[ax+by=c$$$$bx'+(a \bmod b)y'=c
\]
有
\[bx'+(a-\biggl\lfloor\frac a b \biggr\rfloor\times b)y'=c$$$$bx'+ay'-\biggl\lfloor\frac a b \biggr\rfloor\times by'=c$$$$b(x'-\biggl\lfloor\frac a b \biggr\rfloor y')+ay'=c$$$$ay'+b(x'-\biggl\lfloor\frac a b \biggr\rfloor y')=c
\]
即
\[x=y',y=x'-\biggl\lfloor\frac a b \biggr\rfloor y'
\]
例如
\[99x+78y=6
\]
代码如下
struct Extended_gcd{
inline int gcd(int a,int b){
if(!b)
return a;
return gcd(b,a%b);
}
inline void exgcd(int a,int b,int c){
if(!b){
x=c/a,y=0;
return ;
}
exgcd(b,a%b,c);
int t=x;
x=y;
y=t-(a/b)*y;
}
}E;