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