/*
  Author:  Pate Williams (c) 1997

  The following program tests a Chinese remainder
  function. See "A Course in Computational Number
  Theory" by Henri Cohen page 21.
*/

#include <iostream.h>

void EuclidExtended(int a, int b, int &d, int &u, int &v)
{
  int q, t1, t3, v1, v3;

  if (a < 0) a = - a;
  if (b < 0) b = - b;
  u = 1, d = a;
  if (b == 0) {
    v = 0;
    return;
  }
  v1 = 0, v3 = b;
  while (v3 != 0) {
    q = d / v3;
    t3 = d % v3;
    t1 = u - q * v1, u = v1, d = v3, v1 = t1, v3 = t3;
  }
  v = (d - a * u) / b;
}

void BinaryExtended(int a, int b, int &d, int &u, int &v)
{
  int f1, f2, k = 0, q, r, t, t1, t3, v1, v3;

  if (a < 0) a = - a;
  if (b < 0) b = - b;
  if (a < b) t = a, a = b, b = t, f1 = 1; else f1 = 0;
  q = a / b;
  r = a % b;
  a = b;
  b = r;
  if (b == 0) {
    if (f1 == 0)
      u = 1, v = 0, d = a;
    else
      u = 0, v = 1, d = a;
    return;
  }
  while ((a & 1) == 0 && (b & 1) == 0) k++, a >>= 1, b >>= 1;
  if ((b & 1) == 0) t = a, a = b, b = t, f2 = 1; else f2 = 0;
  u = 1, d = a, v1 = v3 = b;
  if ((a & 1) == 1) {
    t1 = 0, t3 = - b;
    goto L5;
  }
  t1 = (1 + b) >> 1, t3 = a >> 1;
  while (t3 != 0) {
    while ((t3 & 1) == 0) {
      t3 >>= 1;
      if ((t1 & 1) == 0) t1 >>= 1;
      else t1 = (t1 + b) >> 1;
    };
  L5:
    if (t3 > 0) u = t1, d = t3; else v1 = b - t1, v3 = - t3;
    t1 = u - v1, t3 = d - v3;
    if (t1 < 0) t1 += b;
  }
  v = (d - a * u) / b, d <<= k;
  if (f2 == 1) t = u, u = v, v = t;
  u -= v * q;
  if (f1 == 0) t = u, u = v, v = t;
}

int inv(int x, int m)
{
  int d, u, v;

  EuclidExtended(x, m, d, u, v);
  if (u < 0) u += m;
  if (d == 1) return u;
  return 0;
}

int binary_inv(int x, int m)
{
  int d, u, v;

  BinaryExtended(x, m, d, u, v);
  if (u < 0) u += m;
  if (d == 1) return u;
  return 0;
}

int InductiveChinese(int k, int *m, int *x)
{
  int d, i, n = m[0], u, v, y = x[0];

  for (i = 1; i < k; i++) {
    EuclidExtended(n, m[i], d, u, v);
    //check for invertibility, gcd(n, m[i]) = 1
    if (d != 1) return 0;
    y = u * n * x[i] + v * m[i] * y;
    n *= m[i];
    y %= n;
  }
  if (y < 0) y += n;
  return y;
}

int BinaryInductiveChinese(int k, int *m, int *x)
{
  int d, i, n = m[0], u, v, y = x[0];

  for (i = 1; i < k; i++) {
    BinaryExtended(n, m[i], d, u, v);
    //check for invertibility, gcd(n, m[i]) = 1
    if (d != 1) return 0;
    y = u * n * x[i] + v * m[i] * y;
    n *= m[i];
    y %= n;
  }
  if (y < 0) y += n;
  return y;
}

void main(void)
{
  const int SIZE = 8192;
  int i, k, m[SIZE], x[SIZE];

  cout << "number of equations = ";
  cin >> k;
  for (i = 0; i < k; i++) {
    cout << "x = ";
    cin >> x[i];
    cout << "modulus = ";
    cin >> m[i];
  }
  cout << "x = " << InductiveChinese(k, m, x) << endl;
  cout << "x = " << BinaryInductiveChinese(k, m, x) << endl;
}