问题引入

求解方程

\[\begin{cases} x &\equiv a_1 \pmod{m_1} \\ x &\equiv a_2 \pmod{m_2} \\ & \vdots \\ x &\equiv a_n \pmod{m_n} \\ \end{cases} \]

其中 \(m_1,m_2,...,m_n\) 两两互质

中国剩余定理 \(\text{CRT}\)

记 \(M = \prod_{i=1}^n m_i,n_i = \frac M {m_i}\)
找到 \(c_i\) 使 \(c_i n_i \equiv 1 \pmod{m_i}\)
那么特解 \(x_0 = \sum_{i=1}^n a_i n_i c_i \pmod M\)
通解表示为 \(x = k M + x_0\) 在模 \(M\) 意义下恒等

扩展 \(\text{exCRT}\)

模数不两两互质的情况
考虑两个方程 \(x \equiv a_1 \pmod{m_1}，x \equiv a_2 \pmod{m_2}\)
化为不定方程 \(x = k_1 m_1 + a_1 = k_2 m_2 + a_2\)
移项得到 \(m_1 k_1 - m_2 k_2 = a_2 - a_1\)
求解这个不定方程，\(g=\gcd(m_1，m_2)\)
则 \(k_1 \frac{m_1}g - k_2 \frac{m_2}g = \frac{a_2 - a_1}g\)
扩欧求特解 \(p_0，q_0\)
通解为 \(p = p_0 + t \frac{m_2}g ，q = q_0 + t \frac{m_1}g\)
那么选取 \(p\) 在模 \(\frac{m_2}g\) 意义下的最小正整数解表示出答案 \(x \equiv m_1 p + a_1 \pmod{lcm(m_1，m_2)}\)
于是我们将原始的两个方程合并成了这样的一个方程
同理与后面的方程进行合并即可

\(\text{Code}\)

#include
#define LL long long
using namespace std;

const int N = 1e5 + 5;
int n;
LL a[N] , b[N];

LL qmul(LL x, LL y, LL P)
{
	LL ret = 0;
	if (y < 0) y = (y % P + P) % P;
	for(; y; y >>= 1)
	{
		if (y & 1) ret = (ret + x) % P;
		x = 2 * x % P;
	}
	return ret;
}

LL exgcd(LL a, LL b, LL &x, LL &y)
{
	if (!b)
	{
		x = 1, y = 0;
		return a;
	}
	LL d = exgcd(b, a % b, x, y);
	LL t = x - a / b * y; x = y, y = t;
	return d;
}

LL exCRT()
{
	LL B = b[1], A = a[1], M, x, y, d, c;
	for(int i = 2; i <= n; i++)
	{
		d = exgcd(A, a[i], x, y);
		c = a[i] / d;
		x = (qmul(x, (b[i] - B) / d, c) + c) % c;
		M = A / d * a[i];
		B = (qmul(x, A, M) + B) % M, A = M;
	}
	return B;
}

int main() 
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%lld%lld", a + i, b + i);
	printf("%lld\n", exCRT());
}