（扩展）中国剩余定理模板

using namespace std;
typedef long long LL;
const int maxn = 15;
LL n, r[maxn], m[maxn];
LL (LL a, LL b, LL &x, LL &y) {
    if(b == 0LL) {x = 1LL; y = 0LL; return a;}
    LL res = ext_gcd(b, a % b, x, y);
    LL tmp = x; x = y, y = tmp - a / b * y;
    return res;
}
LL quick_mul(LL a, LL b, LL mod){
    LL res = 0LL; ///注意是0，不是1
    while(b) { ///按b的二进制展开，然后累加二进制位对应a的幂次，同时取模
        if(b & 1) res =(res + a) % mod; ///b中有1则累加a的值，进行加法运算
        a = (a + a) % mod; ///a每次乘2并取模
        b >>= 1;
    }
    return res;
}
///中国剩余定理：模数两两互质
LL crt(LL *r, LL *m, LL n) {
    LL lcm = 1LL, res = 0LL, M_i, x, y;
    for(LL i = 0; i < n; ++i) lcm *= m[i]; ///先求出所有方程的模数的最小公倍数
    for(LL i = 0; i < n; ++i) {
        M_i = lcm / m[i]; ///除当前方程的模数外的最小公倍数
        ext_gcd(M_i, m[i], x, y);
        x = (x % m[i] + m[i]) % m[i]; ///取最小非负整数解
        ///res = (res + r[i] * M_i * x) % lcm;
        res = (res + quick_mul(quick_mul(r[i], M_i, lcm), x, lcm)) % lcm; ///快速乘法取模，避免直接相乘导致数据溢出
    }
    return res;
}

using namespace std;
typedef long long LL;
const int maxn = 15;
LL T, n, ans, r[maxn], m[maxn];
///求解二元一次方程：ax + by = gcd(a,b)
LL (LL a, LL b, LL &x, LL &y) {
    if(b == 0LL) {x = 1LL; y = 0LL; return a;} ///不妨假设 y=0，则x=1
    LL res = ext_gcd(b, a % b, x, y);
    LL tmp = x; x = y, y = tmp - a / b * y; ///x'=y,y'=x-a/b*y
    return res; ///返回上一个状态
}
///扩展中国剩余定理：模数两两不都互素
LL ext_crt(LL *r, LL *m, LL n) { ///余数：r，模数：m，同余方程个数：n
    LL lcm = m[0], res = r[0], x, y, gcd, mod;
    for(LL i = 1; i < n; ++i) {
        gcd = ext_gcd(lcm, m[i], x, y); ///求最大公约数
        if((r[i] - res) % gcd) return -1; ///无解
        x *= (r[i] - res) / gcd; ///一个解
        mod = m[i] / gcd; ///对应的模数
        x = (x % mod + mod) % mod; ///最小非负整数解
        res = res + lcm * x; ///合并后的方程的余数
        lcm = lcm / gcd * m[i]; ///合并后的方程的模数，先除后乘，避免数据溢出
    }
    return res; ///答案
}