速通中国剩余定理

· · 算法·理论

反正是复习，我长话短说只写这玩意重点了.

CRT

题目

给定 n 组非负整数 m_i, a_i ，求解关于 x 的方程组的最小非负整数解。

\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \dots \\ x \equiv a_n \pmod{m_n} \end{cases}

对于 100 \% 的数据，1 \le n \le {10}^5，1 \le m_i \le {10}^{12}，0\leq a_i \leq 10^{12}，保证所有 m_i 的最小公倍数不超过 {10}^{18}，保证 m 中的元素两两互质。

数据保证有解。

思路

设 M = \prod m_i。

我们对于每个 i \left (1 \leq i \leq n \right )，算出这样的一个 x_i 满足：

\frac{Mx_i}{m_i} \equiv 1 \pmod{m_i}

可以用括欧做出来，然后答案就是：

\sum_{i = 1} ^ n a_ix_i

原理大概就是当前方程的x_i满足模其他几个方程都是 0，我们算出模当前模数为 1 的结果后就满足了当前的方程，最后一个一个加起来就全满足了。

代码

原题曹冲养猪会爆ll，所以代码里开了__int128

#include<bits/stdc++.h>
using namespace std;
#define int __int128
int gcd(int x, int y)
{
    return y == 0 ? x : gcd(y, x % y);
}
int lcm(int x, int y)
{
    return x / gcd(x, y) * y;
}
void exgcd(int a, int b, int &x, int &y) 
{
    if (b == 0) {
        x = 1;
        y = 0;
        return;
    }
    exgcd(b, a % b, x, y);
    int tp = x;
    x = y;
    y = tp - (a / b) * y;
}
pair<int, int> solveeqn(int a, int b, int k)
{
    if (k % gcd(a, b)) {
        return {-1, -1};
    }
    int x0, y0;
    exgcd(a, b, x0, y0);
    int g = gcd(a, b);
    int tp = k / g;
    x0 *= tp;
    y0 *= tp;
    while (x0 < 0) {
        x0 += b / g;
        y0 -= a / g;
    }
    return {x0, y0};
}
signed main()
{
    long long n;
    cin >> n;
    vector<long long> a(n), m(n);
    int s = 1;
    for (int i = 0; i < n; i++) {
        cin >> m[i] >> a[i];
        s *= m[i];
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int tp = solveeqn(s / m[i], m[i], 1).first;
        if (tp == -1) {
            cout << -1 << '\n';
            return;
        }
        ans += a[i] * s / m[i] * tp;
    }
    ans %= s;
    if (ans < 0) {
        ans += s;
    }
    cout << (long long)ans << '\n';
    return 0;
}

EXCRT

题目

给定 n 组非负整数 m_i, a_i ，求解关于 x 的方程组的最小非负整数解。

\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \dots \\ x \equiv a_n \pmod{m_n} \end{cases}

对于 100 \% 的数据，1 \le n \le {10}^5，1 \le m_i \le {10}^{12}，0\leq a_i \leq 10^{12}，保证所有 m_i 的最小公倍数不超过 {10}^{18}。

数据保证有解。

思路

现在里面的数不两两互质了，所以上面的方法是行不通的。

我们先考虑只有两个同余方程的情况：

\begin{cases} x \equiv a \pmod{b} \\ x \equiv c \pmod{d} \end{cases}

这里 x 就能表示成 b \times p + a的形式，也可以表示成 d \times q + c 的形式。

所以我们就能得到关于 p, q 的一个不定方程：

b \times p - d \times q = a - c

扩展欧几里得就可以把 p 和 q 这两个未知数解出来。

那么很容易就能把这两个方程合并为一个方程：

x \equiv b \times p + a \pmod{ \operatorname{lcm}(b, d) }

然后一直合并下去就做完了，喵。

#include<bits/stdc++.h>
using namespace std;
#define int long long
void exgcd(__int128 a, __int128 b, __int128 &x, __int128 &y) // ax+by=gcd(a,b)的解
{
    if (b == 0) {
        x = 1;
        y = 0;
        return;
    }
    exgcd(b, a % b, x, y);
    __int128 tp = x;
    x = y;
    y = tp - (a / b) * y;
}
__int128 gcd(__int128 x, __int128 y)
{
    return y == 0 ? x : gcd(y, x % y);
}
__int128 lcm(__int128 x, __int128 y)
{
    return x / gcd(x, y) * y;
}
pair<__int128, __int128> solveeqn(__int128 a, __int128 b, __int128 k)
{
    if (k % gcd(a, b)) {
        return {-1, -1};
    }
    __int128 x0, y0;
    exgcd(a, b, x0, y0);
    __int128 g = gcd(a, b);
    __int128 tp = k / g;
    x0 *= tp;
    y0 *= tp;
    if (x0 < 0) {
        int tp = (0 - x0 + b / g - 1) / (b / g);
        x0 += tp * (b / g);
        y0 -= tp * (b / g);
    }
    return {x0, y0};
}
signed main()
{
    int n;
    cin >> n;
    vector<int> a(n), m(n);
    for (__int128 i = 0; i < n; i++) {
        cin >> m[i] >> a[i];
    }
    __int128 tpa = a[0], tpm = m[0];
    for (__int128 i = 1; i < n; i++) {
        auto tp = solveeqn(tpm, -m[i], tpa - a[i]);
        tpa -= tpm * tp.first;
        tpm = lcm(tpm, (__int128)m[i]);
        tpa = (tpa + tpm) % tpm;
        if (tpa < 0) {
            tpa += tpm;
        }
    }
    cout << (int)tpa;
    return 0;
}