1、扩展欧几里得
扩欧,扩展gcd,同余方程,二元一次方程、不定方程(exgcd)
一般形式:
[ax+by=c
]
[ax=cpmod{b}
]
上下两个方程可互相转化
考虑对于
[ax+by=c$$$$bx'+(a mod b)y'=c
]
有
[bx'+(a-iggllfloorfrac a b iggr
floor imes b)y'=c$$$$bx'+ay'-iggllfloorfrac a b iggr
floor imes by'=c$$$$b(x'-iggllfloorfrac a b iggr
floor y')+ay'=c$$$$ay'+b(x'-iggllfloorfrac a b iggr
floor y')=c
]
即
[x=y',y=x'-iggllfloorfrac a b iggr
floor 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;