中国剩余定理

【模板】中国剩余定理.cpp

// 要求：a>=0, b>=0
void ext_gcd(ll a, ll b, ll &x, ll &y){
    // 迭代不变量：
    // x*a + b*y == gcd(a,b);
    if(b==0){
        x=1;
        y=0;
        return;
    }
    // ext_gcd(a, a%b, x, y)
    // gcd(a,b) == x*a + y*(a-a/b*b)
    // gcd(a,b) == (x+y)*a + (-a/b*y)b;

    ext_gcd(b, a%b, y, x);
    // x*(a-a/b*b) + b*y = gcd(a,b)
    //x*a + (y-x*a/b)*b
    y -= x*a/b;
}

ll inv(ll x, ll m){
    ll a, b;
    ext_gcd(x, m, a, b);
    a%=m;
    if(a<0) a+=m;
    return a;
}



// pair.first 余数, pair.second 模数
ll crt(const vector<pair<ll,ll>> &a){
    ll prod = 1;
    // 要求：所有模数之积不会溢出
    for(auto x: a) {
        prod *= x.second;
    }
    ll res = 0;
    for(auto x: a){
        auto t = prod/x.second;
        res += x.first * t % prod * inv(t, x.second) % prod; // error-prone
        if(res >= prod) res -= prod;
    }
    return res;
}