题解：P4777 【模板】扩展中国剩余定理（EXCRT）

题意已经够简洁了不再赘述。

如果学过中国剩余定理的话，那么你肯定知道在所有模数 $m_i$ 相互互质一定有解。而这道题的模数不一定两两互质，那我们应该怎么做呢？

先拿两个同余方程： $$\begin{cases} x \equiv a_1 \pmod {m_1} \ x \equiv a_2 \pmod {m_2} \ \end{cases}$$ 我们可以将它转化为： $$\begin{cases} x = k_1 \times m_1 + a_1 \ x = k_2 \times m_2 + a_2 \ \end{cases}$$ $$\therefore k_1 \times m_1 + a_1 = k_2 \times m_2 + a_2 \$$ $$\therefore a_1 - a_2 = k_2 \times m_2 - k_1 \times m_1$$ 这样我们得到了形式为 $a\times x + b \times y = c$ 的式子。由裴蜀定理可以得到，如果 $\gcd(a,b) \mid c$，则肯定有解。

现在我们已知 $a_1$，$a_2$，$m_1$ 和 $m_2$，就可以利用扩欧解出来 $k_1$ 和 $k_2$，然后又可以倒推出 $x$。

此时，我们得到的 $x$ 是模 $\operatorname{lcm}(m_1,m_2)$ 下的唯一解。于是就可以将这两个方程合并成 一个方程。以此类推，我们可以将方程组中 $n$ 个方程合并成一个方程，最后能够得到答案。

完整代码：

#include<bits/stdc++.h>
#define int __int128
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
const int N=1e5+5;
inline void read(int &a){
	a=0;char c;
	bool f=0;
	while((c<'0'||c>'9')&&c!='-')c=getchar();
	c=='-'&&(f=1,c=getchar());
	while(c>='0'&&c<='9')a=a*10+c-'0',c=getchar();
	f&&(a=-a);
}
inline void write(int a){
	if(a<0)a=-a,putchar('-');
	if(a>9)write(a/10);
	putchar(a%10+'0');
}
int n,M=1;
int a[N],m[N];
inline void exgcd(int a,int b,int &x,int &y){
	if(!b){x=1,y=0;return;}
	exgcd(b,a%b,y,x);
	y-=a/b*x;
	return;
}
inline int gcd(int x,int y){return y?gcd(y,x%y):x;}
signed main(){
	IOS;
	read(n);
	for(int i=1;i<=n;i++)read(m[i]),read(a[i]);
	int M=m[1],res=a[1];
	for(int i=2;i<=n;i++){
		int c=res-a[i];
		int d=gcd(M,m[i]);
		int k1,k2;
		exgcd(m[i],M,k2,k1);
		k1=-k1;
		k1=k1*(c/d);
		k2=k2*(c/d);
		M=M*m[i]/d;
		res=(a[i]+(k2*m[i])%M+M)%M;
	}
	write(res);
	putchar('\n');
	return 0;
}

记录。