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;

}

Tìm nghiệm nguyên của phương trình Diophantine bằng C++ (diophantine code)

#include<bits/stdc++.h>

#define X first

#define Y second

using namespace std;

typedef pair<int, int> ii;

int euclid(int a, int b){

    if (b==0) return a;

    return euclid(b, a%b);

}

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

    if (b==0) return aa;

    int div= a/b;

    ii cc(aa.X - div * bb.X, aa.Y - div * bb.Y);

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

}

int main(){

    int a, b, c;

    cin >> a >> b >> c;

    int d= euclid(a, b);

    if (c%d) cout<<"Pt ko co nghiem nguyen";

    else{

        ii p= extended_euclid(a, b, ii(1, 0), ii(0, 1));      

        int q= c/d;

        cout<<"x = "<<p.X*q<<" , "<<"y = "<<p.Y*q;

    }

}

Bài toán 

Xét phương trình ax+by=c (a, b, c > 0). Tìm một cặp nghiệm nguyên (x, y) của phương trình trên. (Phương trình Diophante)

Ghi chú:

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

Cơ sở lý thuyết:

Link Wiki:         Giải thuật Euclid mở rộng