ExCRT笔记

Posted on 2019-02-03 Views:

问题

求满足：

$\begin{aligned} x &\equiv b_1 &\pmod{a_1} \\ x &\equiv b_2 &\pmod{a_2} \\ x &\equiv b_3 &\pmod{a_3} \\ &\ \ \vdots &\\ x &\equiv b_n &\pmod{a_n} \end{aligned}$

的

的值。

ExCRT

当 $a_1, a_2, \cdots, a_n$ 互素的时候显然可以使用中国剩余定理（CRT）解决，时间复杂度为 $O(n\log n)$ 。

考虑不互素的情况，假设已经解决了前 i - 1 个方程，得到的解为 $x_{i - 1}$ ， $\operatorname{lcm}(a_1, \cdots, a_{i - 1}) = m$ 。

那么我们考虑解决

$x_{i - 1} + tm \equiv b_i \pmod{a_i}$

易证得到的解 $x_i = x_{i - 1} + tm$ 不会再和前

个解产生冲突。

稍微移项一下：

$tm \equiv b_i - x_{i - 1} \pmod{a_i}$

用ExGCD解出

即可。

这套方法称为ExCRT（拓展中国剩余定理），复杂度依旧是 $O(n\log n)$ 。~~全面优于CRT。~~

代码：

#include <cstdio>

using namespace std;
typedef long long ll;
const int N = 100010;
int n;
ll a[N], b[N];

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) return x = 1, y = 0, a;
    ll d = exgcd(b, a % b, y, x);
    return y -= a / b * x, d;
}

ll smul(ll x, ll y, ll mod) {
    if (y < 0) return -qmul(x, -y, mod);
    ll ret = 0;
    for (; y; y >>= 1) {
        if (y & 1) ret = (ret + x) % mod;
        x = (x + x) % mod;
    }
    return ret;
}

ll excrt() {
    ll lcm = a[1], t = b[1], x, y;
    for (int i = 2; i <= n; i++) {
        ll d = exgcd(lcm, a[i], x, y);
        x = smul(x, (b[i] - t) / d, a[i]);
        t += x * lcm;
        lcm = lcm / d * a[i];
        t = (t % lcm + lcm) % lcm;
    }
    return t;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld%lld", &a[i], &b[i]);
    printf("%lld\n", excrt());
    return 0;
}