CRT 60求助！

#include<iostream>
using namespace std;
const int N = 15;
int n;
unsigned long long M = 1, a[N], b[N], x[N], y[N], m[N], res;
unsigned long long exgcd(unsigned long long a, unsigned long long b, unsigned long long& x, unsigned long long& y) {
	if (!b) {
		x = 1, y = 0;
		return a;
	}
	unsigned long long d = exgcd(b, a % b, y, x);
	y -= (a / b) * x;
	return d;
}
int main(void) {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> a[i] >> b[i];
		M *= a[i];
	}
	for (int i = 0; i < n; ++i) {
		m[i] = M / a[i];
		unsigned long long x = 0, y = 0;
		unsigned long long d = exgcd(m[i], a[i], x, y);
		x /= d;
		res += b[i] * m[i] * x;
	}
	cout << (res % M + M) % M << endl;
	return 0;
}