设 ans 为满足前 n - 1个同余方程的解，lcm是前n - 1个同余方程模的最小公倍数，求前n个同余方程组的解的过程如下：
①设lcm * x + ans为前n个同余方程组的解，lcm * x + ans一定能满足前n - 1个同余方程；
②第 n 个同余方程可以转化为a[n] * y + b;
合并①②得：lcm * x + ans = a[n] * y + b; => lcm * x - a[n] * y = b - ans（可以用拓展欧几里得求解x和y）
但是拓展欧几里得要求取余的数是正数，我们可以转化上面的方程为lcm * x + a[n] * -y = b - ans（后面我们用x得到解，所以不关心y的正负）
解得一组x和y;
x += k * (a[n] / gcd);（k为任意整数）
我们可以求得最小非负数x，在带入①得到前n个同余方程的最小非负数解；
代码如下：
| Accepted | 3579 | 15MS | 1368K | 1112 B | G++ |
#include "bits/stdc++.h"
using namespace std;
int a[], b[];
// 拓展欧几里得C++模板
int ex_gcd(int a, int b, int &x, int &y) {
if (b == ) {
x = ;
y = ;
return a;
}
int ans = ex_gcd(b, a % b, y, x);
y -= a / b * x;
return ans;
}
int solve(int n) {
// 任何数对1取余都是0,所以初始化ans = 0, lcm = 1;
int x, y, ans = , lcm = ;
for (int i = ; i < n; i++) {
int gcd = ex_gcd(lcm, a[i], x, y);
if ((b[i] - ans) % gcd) {
return -;
}
// 拓展欧几里得求得的x和y是对于gcd而言的。乘完之后才是对于 (b[i] - ans) 的 x
x *= (b[i] - ans) / gcd;
a[i] /= gcd;
// 使 x 成为最小非负数解
x = (x % a[i] + a[i]) % a[i];
// 更新ans
ans += x * lcm;
// 更新lcm
lcm *= a[i];
}
// 本题要求最小正整数解，如果ans是0，要加一个最小公倍数也就是lcm
return ans ? ans : lcm;
}
int main() {
int t, n, ca = ;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = ; i < n; i++) {
scanf("%d", &a[i]);
}
for (int i = ; i < n; i++) {
scanf("%d", &b[i]);
}
printf("Case %d: %d\n", ca++, solve(n));
}
return ;
}