/*
*/
#include <iostream>
using namespace std;

/*
注意到對于gcd(a,b) = d 我們對(a, b)用歐幾里德輾轉相除會最終得到
(d, 0)此時對于把a =d, b = 0 帶入a*x + b*y = d，顯然x = 1，y可以為任意值，
這里y可以為任意值就意味著解會有無數個。我們可以用a = d, b = 0的情況逆推出來
任何gcd(a, b) = d 滿足a*x + b*y = d的解。如果x0, y0是b*x + (a%b)*y = d 的解，
那么對于a*x + b*y = d的解呢？
b*x0 + (a%b)*y0 = d => b*x0 + (a - [a/b]*b)*y0 = a*y0 + b*(x0 - [a/b]*y0)，
所以a*x + b*y = d的解x1 = y0， y1 = x0 - [a/b]*y0; 這樣我們可以程序迭帶了。
*/
int extEuclid(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int d = extEuclid(b, a % b, x, y);
    int iTemp = x;
    x = y;
    y = iTemp - (a / b)* y;
    return d;
}
//解同余方程ax = b(mod n) (返回最小的正數x)

int modularLinearEquation(int a, int b, int n)
{
    //等價于求ax + cn = b;
    //先求a*x1 + c1*n = gcd(a, n)
    int x, y, d;
    d = extEuclid(a, n, x, y);
    if (b % d != 0)
       return -1;
    x = x * (b / d);
    x = (( x % n) + n) % n;
    return x;
}

//中國剩余定理，推導都是數學
int solModularEquations(int b[], int m[], int k)
{

    int iTemp;
    int y;
    int result;

    int M = 1;
    for (int i = 0; i < k; i++)
      M *= m[i];

    result = 0;
    for (int i = 0; i < k; i++)
    {
      iTemp = M / m[i];
      y = modularLinearEquation(iTemp, 1, m[i]);
      result = (result + b[i] * iTemp * y) % M;
    }
    return result;
}

int main()
{
    int x, y , d;
    d = extEuclid(1001, 767, x, y);
    cout << x << endl;
    cout << y << endl;
    cout << d << endl;
    cout << "1001 * x + 767 * y = " << (1001 * x + 767 * y) << endl;
    cout << modularLinearEquation(3, 2, 100) << endl;
    return 0;
}