前往：我自己搭建的博客
题目
洛谷P1495中国剩余定理(CRT)
题解
CRT要求所有模数两两互质。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=12;
int n;
ll M=1,x,y,ans;
ll a[maxn],m[maxn];
void exgcd(ll a,ll b)
{
if(!b) {x=1,y=0; return;}
exgcd(b,a%b);
ll z=x; x=y; y=z-(a/b)*y;
}
inline ll inv(ll a,ll b) {exgcd(a,b); return (x%b+b)%b;} //求逆元
inline ll CRT()
{
for(int i=1;i<=n;i++) M*=m[i];
for(int i=1;i<=n;i++)
{
ll Mi=M/m[i],ti=inv(Mi,m[i]);
ans=(ans+a[i]*Mi*ti%M)%M;
}
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld%lld",&m[i],&a[i]);
printf("%lld\n",CRT());
return 0;
}
