中国剩余定理

设 $m_1,m_2,…,m_n$ 是两两互质的整数，$m=\prod_{i=1} ^n m_i$，

$M_i=m/m_i$，

$t_i$是线性同余方程$M_it_i \equiv 1(mod\ m_i)$的一个解。

对于任意的$n$个整数 $a_1,a_2,…,a_n$方程组

$x = \sum _{i=1}^n a_iM_it_1$ 是原方程的一个解.

代码实现

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=15;
LL a[N],m[N];
LL exgcd(LL a,LL b,LL &x,LL &y)
{
	if(!b)
	{
		x=1,y=0;
		return a;
	}
	else
	{
		LL d=exgcd(b,a%b,y,x);
		y=y-a/b*x;
		return d;
	}
}
int main()
{
	int n;
	cin>>n;
	LL M=1;
	for(int i=1;i<=n;i++)
	{
		cin>>m[i]>>a[i];
		M*=m[i];//读入m[i]的同时计算M 
	}
	LL res=0;
	for(int i=1;i<=n;i++)
	{
		LL Mi=M/m[i];//计算Mi
		LL ti,y;
		exgcd(Mi,m[i],ti,y); //ti*Mi+y*mi=1
		res+=a[i]*Mi*ti; 
	}
	cout<<(res%M+M)%M<<endl;
	return 0;
}