Giải hệ phương trình thặng dư Trung Hoa bằng C++ (chinese remainder theorem code)

 Bài toán 

Ghi chú:

Hàm extended_euclid đã được kiểm tra trên UVA
Code by Nguyễn Công Cường

#include<bits/stdc++.h>

#define X first

#define Y second

using namespace std;

typedef pair<int, int> ii;

ii extended_euclid(int a, int b, ii aa, ii bb){

    if (b==0) return aa;

    int div= a/b;

    ii ab(aa.X - div*bb.X, aa.Y - div*bb.Y); // ab ~ aa % bb

    return extended_euclid(b, a%b, bb, ab);

}

int module_inverse(ii p, int m){

    int M= p.X;

    return (M%m+m)%m;

}

const int N= 1000111;

int a[N], m[N], M[N], y[N];

int n, p= 1, x= 0;

int main(){

    //input

    cout<<"n = "; cin >> n;

    for(int i=1; i<=n; i++)

        cin >> a[i] >> m[i];

       

    //process

    for(int i=1; i<=n; i++)  p *= m[i];

    for(int i=1; i<=n; i++){

   

        M[i]= p / m[i];

        if (__gcd(M[i], m[i]) != 1){

            cout<<"Ko tim duoc nghiem do ko ton tai nghich dao modun";

            exit(0);

        }

        y[i]= module_inverse(extended_euclid(M[i], m[i], ii(1,0), ii(0,1)), m[i]);

        x = (x + a[i]*M[i]*y[i])%p;  

    }

    //output

    cout << x;

}