Translate

Views

Wednesday, September 28, 2022

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;
}

No comments: