考虑递推
假设对于前i个线性同余方程，我们得到了x的一组解
对于第i+1个方程，我们需要求出 \(x+t*M \equiv a_{i+1} (mod \,\, m_{i+1})\) 中的t值
其中M为前i个方程的最小公倍数
exgcd 求解即可
这样重复n次即可得到最终答案
扩展CRT
发布时间 2023-06-15 20:16:42作者: Flandreqwq
考虑递推
假设对于前i个线性同余方程，我们得到了x的一组解
对于第i+1个方程，我们需要求出 \(x+t*M \equiv a_{i+1} (mod \,\, m_{i+1})\) 中的t值
其中M为前i个方程的最小公倍数
exgcd 求解即可
这样重复n次即可得到最终答案