/*
	g++ main.cpp -o main -O2 -std=c++11 -lgmp
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <fstream>
#include <string.h>
#include <stdlib.h>
#include <time.h>

using namespace std;

/*
	Question:
		What is the lowest x that fits the modulo rules?

	Example:
		x = 1 (mod 3)
		x = 4 (mod 5)
		x = 6 (mod 7)
		x = 7 (mod 11)
		x = 5 (mod 13)
		x = 5 (mod 19)

	Step 1:
		x1 = 3k + 1

	Step 2:
		3k + 1 = 4 (mod 5)
		3k = 3 (mod 5)
		3k = 5L + 3
		k = 5L + 1

		x = 3(5L + 1) + 1
		x = 15L + 4

	Step 3:
		15L + 4 = 6 (mod 7)
		15L = 2 (mod 7)
		1L = 2 (mod 7)
		1L = 7m + 2
		L = 7m + 2

		x = 15(7m + 2) + 4
		x = 105m + 34

	Step 4
		105m + 34 = 7 (mod 11)
		105m = 6 (mod 11)
		6m = 6 (mod 11)
		6m = 11n + 6
		m = 11n + 1

		x = 105(11n + 1) + 34
		x = 1155n + 139

	Step 5:
		1155n + 139 = 5 (mod 13)
		1155n = 9 (mod 13)
		11n = 9 (mod 13)
		11n = 13p + 9
		n = 13p + 2

		x = 1155(13p + 2) + 139
		x = 15015p + 2449

	Step 6:
		15015p + 2449 = 5 (mod 19)
		15015p = 7 (mod 19)
		5n = 7 (mod 19)
		5n = 19q + 7
		p = 19q + 9

		x = 15015(19q + 9) + 2449
		x = 285285q + 137584
*/

struct Formula {
	long long remainder;
	long long modulo;
};

typedef vector<Formula> Rules;

long long gcd(long long a, long long b) {
	long long c;

	while ( a != 0 ) {
		c = a;
		a = b % a;
		b = c;
	}

	return b;
}

/*
	Get lowest value that fits the rules (Bruteforce)
*/
long long f2(const Rules &r) {
	int i, id;
	long long v;

	//Init
	id = r.size() - 1;
	v = r[id].remainder;

	for(i = 0; i < r.size(); i++) {
		// Debug
		//cout << v << " % " << r[i].modulo << " = " << v % r[i].modulo << endl;

		if(v > 10000000)
			return -1;

		if(v % r[i].modulo != r[i].remainder) {
			v += r[id].modulo;
			i = -1;
		}
	}

	return v;
}

/*
	Find smallest x as a integer

	Formula:
		xa = b + cy
*/
long long getRemainder(long long a, long long b, long long c) {
	long long x, y;

	if(a == 0)
		return -1; //No answer found

	for(y = 0; y <= c; y++) {
		x = b + (c * y);

		if(x % a == 0) {
			x = x / a;

			// Debug
			//cout << "gcd(" << a << ", " << b << ") = " << gcd(a, b) << endl;
			//cout << a << " * " << x << " = " << b << " + (" << y << " * " << c << ")" << endl;
			//cout << "------------------------" << endl;

			return x;
		}
	}

	return -1; //No answer found
}

/*
	Get lowest value that fits the rules
*/
long long f(const Rules &r) {
	int i;
	long long x, y, x2, y2;
	Formula f;

	f = r[0];
	x = f.remainder;
	y = f.modulo;

	for(i = 1; i < r.size(); i++) {
		f = r[i];
		y2 = f.modulo;

		x2 = (((((x / y2) + 1) * y2) + f.remainder) - x) % y2;
		x2 = getRemainder(y % y2, x2, y2);

		if(x2 == -1)
			return -1; // No answer possible

		// Update
		x += y * x2;
		y = y * y2;
	}

	return x;
}

int main() {
	//Rules r = {{1, 3}, {4, 5}, {6, 7}};
	//Rules r = {{1, 3}, {4, 5}, {6, 7}, {7, 11}};
	//Rules r = {{1, 3}, {4, 5}, {6, 7}, {7, 11}, {5, 13}};
	Rules r = {{1, 3}, {4, 5}, {6, 7}, {7, 11}, {5, 13}, {1, 19}};

	cout << "Result = " << f(r) << " " << f2(r) << endl;

	return 0;
}