本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-05-27 22:28:05

前言：

看了 $\color{black}\text{W}\color{red}\text{YXkk}$ 和 $\color{black}\text{阮}\color{red}\text{行止}$ 的题解我总算是会了

正文：

先考虑只有两个方程的情况：
$\begin{cases} x \equiv r_1 (\mod m_1)\ x \equiv r_2 (\mod m_2) \end{cases}$
可以转化为：
$\begin{cases} x = r_1 + k_1m_1\ x = r_2 + k_2m_2 \end{cases}$
显然可得：
$r_1 + k_1m_1 = r_2 + k_2m_2$
移项之后：
$k_1m_1 + k_2(-m2) = r_2 - r_1$
然后解出 $k_1$ 和 $k_2$（求解这种方程的代码下附，其实这么简单的东西自己推一下也能推出解法）
然后 $x$ 就是 $r_1 + k_1m_1$（没错，不用 $k_2$ 和 $m_2$ 也行）

然后就是合并这两个方程，这里用到了一个定理：
$\begin{cases} x \equiv r_1 (\mod m_1)\ x \equiv r_2 (\mod m_2) \end{cases}$
设这两个方程有一个特解 $x_0$，满足
$\begin{cases} x_0 \equiv r_1 (\mod m_1)\ x_0 \equiv r_2 (\mod m_2) \end{cases}$
那么它们的通解 $x$ 满足
$x \equiv x_0 (\mod lcm(m_1,m_2))$
这样就和并成了一个方程，但是这个做法我不会证明

现在就是把方程组的每个方程都压入队列中，每次取队首的两个方程进行合并再压入队列中，直到只剩一个方程。显然这个方程的解就是最终的解。

额外：

放一份求解形如 $ax+by=c$ 这样的方程的代码（已知 $a,b,c$）

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	typedef long long ll;
	ll exgcd(ll a,ll b,ll& x,ll& y)
	{
		if(!b)
		{
			x=1;
			y=0;
			return a;
		}
		ll ans=exgcd(b,a%b,x,y);
		ll tmp=x;
		x=y;
		y=tmp-a\/b*y;
		return ans;
	}
	ll a,b,c,x0,y0,x,y;
	void main()
	{
		printf("Solving ax+by=c\n");
		printf("a: ");
		scanf("%lld",&a);
		printf("b: ");
		scanf("%lld",&b);
		printf("c: ");
		scanf("%lld",&c);
		int d=exgcd(a,b,x0,y0);
		if(c%d!=0)
		{
			printf("No\n");
			return;
		}
		int k=c\/d;
		x=x0*k;
		y=y0*k;
		printf("%lld * %lld + %lld * %lld = %lld",a,x,b,y,c);
	}
}
int main()
{
	Main::main();
	return 0;
}

注意：

exgcd 的结果可能是负数

代码：

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	const int maxn=1e5+5;
	typedef long long ll;
	typedef __int128 ll128;
	typedef pair<ll128,ll128> pr;
	ll gcd(ll a,ll b)
	{
		return !b?a:gcd(b,a%b);;
	}
	ll lcm(ll a,ll b)
	{
		return a\/gcd(a,b)*b;
	}
	ll exgcd(ll a,ll b,ll& x,ll& y)
	{
		if(!b)
		{
			x=1;
			y=0;
			return a;
		}
		ll ans=exgcd(b,a%b,x,y);
		ll tmp=x;
		x=y;
		y=(ll128)tmp-ll128(a\/b)*(ll128)y;
		return ans;
	}
	pr axbyc(ll a,ll b,ll c)
	{
		ll x0,y0;
		ll d=exgcd(a,b,x0,y0);
		ll128 k=c\/d;
		ll128 x=(ll128)x0*k;
		ll128 y=(ll128)y0*k;
		return make_pair(x,y);
	}
	int n;
	ll128 m[maxn],r[maxn];
	queue<pr> equ;
	ll128 gsc(ll128 a,ll128 b,ll128 mod)
	{
		ll128 ret=0;
		while(b)
		{
			if(b&1)ret=(ret+a)%mod;
			ret=ret*2%mod;
			b>>=1;
		}
		return ret;
	}
	void main()
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			ll mi,ri;
			scanf("%lld%lld",&mi,&ri);
			equ.push(make_pair(mi,ri));
		}
		while(equ.size()>1)
		{
			pr _=equ.front();
			equ.pop();
			pr __=equ.front();
			equ.pop();
			ll128 m1=_.first;
			ll128 r1=_.second;
			ll128 m2=__.first;
			ll128 r2=__.second;
			pr ___ = axbyc(m1,-m2,r2-r1);
			ll128 k1=___.first;
			ll128 x=r1+(ll128)k1*(ll128)m1;
			equ.push(make_pair(lcm(m1,m2),(x%(ll128)lcm(m1,m2)+(ll128)lcm(m1,m2))%(ll128)lcm(m1,m2)));
		}
		printf("%lld",(ll)equ.front().second);
	}
}
int main()
{
	Main::main();
	return 0;
}