前置技能
了解同余方程并掌握扩展欧几里得算法。
具体实现
中国剩余定理大概就是解决很多个(displaystyle x≡a_i( ext{mod } b_i))的方程的最小整数解问题，我们先来考虑(b)都互质的情况，考虑构造答案我们发现如果令(lcm = b_1 × b_2 × … ×b_n)可以得知 (displaystylefrac{lcm}{b_i})对于所有其他的(b)取模都是(0)，那么只考虑模当前项为(1)的时候的答案，即求(ans_i × displaystylefrac{lcm}{b_i} ≡ 1( ext{mod }b_i))，设对于第(i)项( ext{exgcd})求出的答案为(ans_i) 则最终答案为 (displaystylesum_{i = 1}^na_i imes ans_i imesfrac{lcm}{b_i}( ext{mod lcm}))。
但是朴素的CRT只能解决(b)都互质的问题，如果不互质的话那它就无能为力了，所以我们现在来考虑(b)不互质的情况，考虑合并两个方程：
我们把这个东西写成不定方程的形式，那么：
对于这个式子我们可以( ext{exgcd})解出(x_1)的值，那么合并之后的方程就是：
例题
「NOI2018」屠龙勇士，题意是你有一些剑，你需要按顺序杀一些龙，杀了一条龙之后你的剑会消失，同时获得一把新的剑，你每次会选择攻击力不高于当前龙生命值攻击力最大的剑攻击龙(x)次，第(i)条龙的生命值是在模(p_i)意义下的，求最小攻击次数(x)。
因为杀龙的过程是个固定的，我们可以用一个Multiset处理出杀每条龙的剑，处理出来之后我们发现就是要求很多个形如(kx≡a_i( ext{mod } p_i))的方程，那么直接用中国剩余定理合并就好了，但是这个是要求(a_ile p_i)的，我们观察数据表格可以发现所有不满足(a_ile p_i)的方程都满足(p_i=1)，那么我们大力特判掉就ok了，代码戳我。
总结
其实这个东西遇到合并方程的时候就可以直接上了，还有一个比较有用的东西就是在MTT的时候我们可以把模几个不同的NTT素数的结果用中国剩余定理合并，这样就提高了FFT的精度，也可以做任意模数NTT了。