中国剩余定理

注意公式。

中国剩余定理

0. 前置知识

逆元。

我的逆元 Blog

1. 处理的问题

$m_1,m_2,..,m_n$ 两两互质。

求 $x\in \text{Z}$，使：

$$\begin{array}{ll} x=a_1\pmod {m_1}\\ x=a_2\pmod {m_2}\\ ...\\ x=a_n\pmod {m_n} \end{array}$$

2. 解决的方法

设 $M=m_1m_2…m_n$。

令 $M_i=\dfrac{M}{m_i},t_i=M_i^{-1}\pmod {m_i}$。

那么，$x=\sum_{i=1}^{n} {a_i t_i M_i}$。

证明略。（背就行了 逃）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

typedef long long ll;
const int N=12;
int n,m[N],b[N];

void exGCD(ll a,ll b,ll &x,ll &y)
{
	if (!b)
	{
		x=1;y=0;
		return;
	}
	exGCD(b,a%b,y,x);
	y-=a/b*x;
	return;
}

int main()
{
	cin>>n;
	for (int i=1;i<=n;++i)
		scanf("%d %d",&m[i],&b[i]);
	ll M=1,res=0;
	for (int i=1;i<=n;++i) M*=m[i];
	for (int i=1;i<=n;++i)
	{
		ll Mi=M/m[i],ti,x;
		exGCD(Mi,m[i],ti,x);
		res+=b[i]*Mi*ti;
	}
	printf("%lld\n",(res%M+M)%M);
	return 0;
}