中国剩余定理CRT笔记

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

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;
}