exCRT 模板

用于求解线性同余方程组。

查看代码

typedef __int128 L;
typedef long long LL;
LL gcd (LL a, LL b) { return b ? gcd(b, a % b) : a; }
LL lcm (LL a, LL b) { return a / gcd(a, b) * b; }
LL exgcd (LL a, LL b, LL &x, LL &y)
{
    if (!b) return x = 1, y = 0, a;
    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
LL CRT()
{
    LL b = w[1], p = v[1], x, y;
    for (int i = 2; i <= n; ++i)
    {
        LL d = gcd(v[i], p);
        if ((w[i] - b) % d) return void(puts("-1"));
        exgcd(p / d, v[i] / d, x, y);
        x = ((L)(w[i] - b) / d * x % v[i] + v[i]) % v[i];
        L t = b + (L)p * x;
        p = lcm(p, v[i]);
        b = (t % p + p) % p;
    }
    return 0;
}