普通CRT是比较好写的，再加上第三节课大多数题目有excrt作为前置芝士，所以写一下excrt
发现excrt用拼音直接打出来是恶心CRT
对于n个同余方程，求解是困难的，我们考虑n=2的情况
我们不难发现$ x=a_1\times k_1+b_1=a_2\times k_2+b_2$ (\(k_1\) \(k_2\) 为任意一个数)
移项：$ a_1 \times k_1-a_2\times k_2=b_2-b_1$
我们设 \(d=gcd(a_1,a_2) ,p_1=\frac {a_1} {d}, p_2=\frac {a_2} {d}\)
原式等于： $ p_1\times k_1-p_2\times k_2=\frac{b_2-b_1}{d}$
不拿看出：\(\frac{b_2-b_1}{d}\)不为整数时无解
我们再设：$ k_1 =\frac{b_2-b_1}{d} \times \alpha_1,k_2 =-\frac{b_2-b_1}{d} \times \alpha_2$
那么原式就变成了：\(p_1\times\alpha_1+p_2\times\alpha_2=1\)
我们可以用exgcd解出\(\alpha_1 ,\alpha_2\)
然后就可以解出\(k_1,k_2\)
然后就可以解出x
我们就得到了x的一个特解
然后就可以求出来一个通解：\(X=x+lcm(a_1,a_2)\times k\)
那么现在的问题就变成了：怎么求普遍的n时的解法呢？
我们可以先求出来两个方程的解，用这个解ans去构造一个新的同余方程即：
\(ans\equiv k (mod\ lcm(a_1,a_2))\)（k需要我们自己求）
然后再将这个同余方程和下一个同余方程求解，然后就得出来答案了
n小于等于1e5，记得开__int128