首页 > itarticle > 孙子定理

孙子定理

admin 11月 13, 2020 0

同余方程组

已知x%Ai=Bi 求x

过程

令$ M=A1*A2···An ,Mi=M/Ai$，ti为Mi的数论倒数

$x=∑Bi ti Mi %M$

数论倒数可用费马小定理或者扩欧求解。


#define LL long long
using namespace std;
LL A[25],B[25];
int (){
    ios::sync_with_stdio(false);
    int n; LL M=1;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>A[i]>>B[i];
        M*=A[i];
    }
    LL ans=0;
    for(int i=1;i<=n;i++){
        LL Mi=M/A[i];
        LL t=1;
        while(t*Mi%A[i]!=1) t++;
        ans+=t*Mi*B[i];
        ans%=M;
    }
    cout<<ans;
    return 0;
}