萌新求助 EXCRT WA#14

#include <cstdio>

typedef long long ll;
typedef unsigned long long ull;
#define min(a, b) (((a) < (b)) ? (a) : (b))
#define max(a, b) (((a) > (b)) ? (a) : (b))

inline ll read()
{
	char c = getchar();
	ll ret = 0, t = 1;
	while ((c < '0' || c > '9') && c != '-') c = getchar();
	if (c == '-') t = -1, c = getchar();
	while (c >= '0' && c <= '9') ret = ret * 10 + c - '0', c = getchar();
	return ret * t;
}

ll mul(ll a, ll b, ll p)
{
    ll l = a * (b >> 25LL) % p * (1LL << 25) % p, r = a * (b & ((1LL << 25) - 1)) % p;
    return (l + r) % p;
}

ll exgcd(ll a, ll b, ll& x, ll& y)
{
	if (b)
	{
		ll d = exgcd(b, a % b, y, x);
		y -= (a / b) * x; return d;
	}
	else { x = 1, y = 0; return a; }
}

ull gcd(ull a, ull b)
{
	if (b) return gcd(b, a % b);
	return a;
}
ull lcm(ull a, ull b)
{
	return a / gcd(a, b) * b;
}


ll EXCRT(int N, ll* A, ll* B)
{
	int i; ll X = A[1] % B[1], t, k; ull M = B[1];
	for (i = 2; i <= N; ++i)
	{
		ll gc = exgcd(M, B[i], k, t); t = ((A[i] - X) % B[i] + B[i]) % B[i], k = (k % B[i] + B[i]) % B[i];
		if (t % gc) return -1;
		k = mul(k, t / gc, B[i]), X = X + k * M, M = lcm(M, B[i]), X = (X % M + M) % M;
	}
	return X;
}

#define MAXN 100005
int N; ll a[MAXN], b[MAXN];

int main()
{
	N = read(); int i;
	for (i = 1; i <= N; ++i) b[i] = read(), a[i] = read();
	printf("%lld", EXCRT(N, a, b));
	return 0;
}