概览

数论

$a*x1+b*y1=gcd(a,b)=gcd(b,a\%b)=b*x2+(a\%b)*y2 \\可以推出x1=y2 , y1=x2-a/b*y2$

$有一些线性同余方程\\ X=b1 (mod\ a_1)\\ X=b2 (mod\ a_2)\\ ...\\ X=bn (mod\ a_n)\\ 对于前面第一个方程，我们可以用exgcd求出一个X满足一式$

$设X_{1}=a1*y1+b1,若存在X满足二式，则 \\a1*y1+b1=b2 (mod\ a2) \\这个式子也就是a1*y1+a2*y2=b2-b1,当且仅当gcd(a1,a2)|b2-b1时有解$

$那么我们就可以用exgcd求出y1的解:y1=(b2-b1)*a1^{-1} (mod\ a2)\\其中y1\in[0,a2)\\进而求出X_1$

一式二式合并后是什么呢？我们可以证明在lcm(a1,a2)中有且仅有一个X满足条件

$由此我们得到一个新方程X=X_1(mod\ lcm(a1,a2))$