Hdu 3579(扩展中国剩余定理)

模数不互质的中国剩余定理模板，证明见此
#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
LL kase, n, mi[10], ai[10];
LL gcd(LL a, LL b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
LL lcm(LL a, LL b) {
    return a * b / gcd(a, b);
}
void exgcd(LL a, LL b, LL &x, LL &y) {
    if (b == 0) {
        x = 1, y = 0;
        return ;
    }
    exgcd(b, a % b, x, y);
    LL tmp = x;
    x = y, y = tmp - (a / b) * y;
}
void clean() {}
int solve() {
    scanf("%lld", &n);
    clean();
    LL fl = false;
    for (LL i = 1; i <= n; i++) scanf("%lld", &mi[i]);
    for (LL i = 1; i <= n; i++) scanf("%lld", &ai[i]);
    LL ll = mi[1];//所有的lcm
    for (LL i = 2; i <= n; i++) {//合并n-1次
        ll = lcm(ll, mi[i]);
        LL x1, x2, a = mi[i - 1], b = mi[i], c = ai[i] - ai[i - 1]; 
        LL g = gcd(a, b); 
        if (c % g != 0) {fl = true; break;}
        a /= g, b /= g, c /= g;
        exgcd(a, b, x1, x2);
        b = (b > 0) ? b : -b;
        x1 = (x1 * c % b + b) % b;
        mi[i] = lcm(mi[i], mi[i - 1]);
        ai[i] = ai[i - 1] + mi[i - 1] * x1;
    }
    if (fl) printf("Case %lld: -1\n", kase); else {//计算最后一个
        LL x1, x2, a = 1, b = -mi[n], c = ai[n]; 
        LL g = gcd(a, b); 
        a /= g, b /= g, c /= g;
        exgcd(a, b, x1, x2);
        b = (b > 0) ? b : -b;
        x1 = (x1 * c % b + b) % b;
        if (x1 == 0) {
            printf("Case %lld: %lld\n", kase, ll);
        } else printf("Case %lld: %lld\n", kase, x1);
    }
    return 0;
}
int main() {
    kase = 0;
    LL T; scanf("%lld", &T);
    while (T--) kase++, solve();
    return 0;
}