中国剩余定理
AcWing 204. 表达整数的奇怪方式 原题链接
输入格式
第11 行包含整数 nn。
第 22..n+1n+1行：每 i+1i+1 行包含两个整数aiai和mimi,数之间用空格隔开。
输出格式
输出最小非负整数 xx，如果 xx 不存在，则输出 −1−1。 如果存在 xx，则数据保证 xx 一定在64位整数范围内。
数据范围
1≤ai≤231−11≤ai≤231−1, 0≤mi<ai0≤mi<ai 1≤n≤251≤n≤25
输入样例：
2
8 7
11 9
输出样例：
31
static long x;
static long y;
public static long exgcd(long a, long b) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
long d = exgcd(b, a % b);
long tmp = x;
x = y;
y = tmp - a / b * y;
return d;
}
public static void main(String[] args) {
int n = in.nextInt();
boolean hasAnswer = true;
long a1 = in.nextLong();
long m1 = in.nextLong();
for (int i = 1; i < n; i++) {
long a2 = in.nextLong();
long m2 = in.nextLong();
long d = exgcd(a1, a2);
if ((m2 - m1) % d != 0) {
hasAnswer = false;
break;
}
x *= (m2 - m1) / d;
long t = a2 / d;
x = (x % t + t) % t;
m1 = a1 * x + m1;
a1 = Math.abs(a1 * a2 / d);
}
if (hasAnswer) {
out.println((m1 % a1 + a1) % a1);
}else {
out.println("-1");
}
out.flush();
out.close();
}