题解
参考wiki-中国剩余定理
给出公式:
$$x=\sum_{1}^{n} b_iA_iA_i^{-1}$$
$A_i=a_{1}a_{2}…a_{i-1}a_{i+1}…a_{n}$
$A_i^{-1}$是$A_i$在模$a_i$下的乘法逆元
如何求$A_i^{-1}$
设我们要求的$A_i^{-1}=x$
$$A_ix≡1(\ mod\ a_i)$$
$$A_ix+a_{i}y≡1(\ mod\ a_i)$$
因为Ai与ai互质 所以gcd(Ai,ai)=1,
$$A_ix+a_{i}y≡gcd(A_i,a_i)(\ mod\ a_i)$$
$$A_ix+a_{i}y=gcd(A_i,a_i)$$
如此上式便是标准的扩展欧几里得公式,运用扩欧可以求出x,y
但注意这个x是没有模a_i下求出来的,会有很多个或者说很大
这时候我们按照题目要求取最小的那个正整数
即
$$x=(x\%a_i+a_i)\%a_i$$(+a_i)为了防止x是负数
代码
//x≡b(mod a)
#include<iostream>
using namespace std;
#include<algorithm>
typedef long long intt;
typedef pair<intt,intt> II;
intt gcd;
II exgcd(intt a,intt b){
if(b==0){
gcd=a;
return {1,0};
}else{
II temp=exgcd(b,a%b);
return{temp.second,temp.first-a/b*temp.second};
}
}
int main(void){
intt n,sum=0,A=1,Ai;
II temp;
cin>>n;
intt a[n],b[n];
for(int i=0;i<n;i++){
cin>>a[i]>>b[i];
A*=a[i];
}
for(int i=0;i<n;i++){
Ai=A/a[i];
temp=exgcd(Ai,a[i]);//Ai*x≡1(mod ai)->Ai*x+ai*y≡1(mod ai)
//因为Ai与a[i]互质 所以gcd(Ai,ai)=1,所以Ai*x+ai*y=gcd(Ai,ai)即可用exgcd求解
sum+=temp.first*Ai*b[i];
}
cout<<(sum%A+A)%A<<endl;//任意res + k*M 都满足要求,因为题目中每个等式分别模mi
}