扩展中国剩余定理

防爆long long 代码参考：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41130487

#include
typedef __int128 ll;
using namespace std;
 
void read(__int128 &x)//输入
{
    x = 0;
    int f = 1;
    char ch;
    if((ch = getchar()) == '-') f = -f;
    else x = x*10 + ch-'0';
    while((ch = getchar()) >= '0' && ch  9) print(x/10);
    putchar(x%10 + '0');
}
 
void exgcd(ll a,ll b,ll &g,ll &x,ll &y) {
    if (b == 0) {
        g = a;
        x = 1;
        y = 0;
        return;
    }
    exgcd(b,a%b,g,y,x);
    y-=(a/b)*x;
}
 
bool flag = false;
ll a1,a2,n1,n2;
ll abs(ll x) {
    return x>0?x:-x;
}
 
void china() {
    ll d = a2 - a1;
    ll g,x,y;
    exgcd(n1,n2,g,x,y);
    if (d % g == 0) {
        x = ((x*d/g)%(n2/g)+(n2/g))%(n2/g);
        a1 = x*n1 + a1;
        n1 = (n1*n2)/g;
    }
    else
        flag = true;
}
 
ll n,m;
ll as[100001];
ll ns[100001];
ll realchina() {
    a1 = as[0];
    n1 = ns[0];
    for (ll i = 1;i