前言

蒟蒻的数论简直太垃圾了，什么都不会，所以要从最简单的东西开始......要是出现错误，请在下方评论区指出。

为了让某一天 或者每天 犯傻的 $CXY07$ 可以看得懂，一切都用尽我所能用最 sb 显然的语言解释，巨佬们不要嫌我啰嗦 $qwq$

正题

参考博客

上次学了拉格朗日插值，听某神仙学长说中国剩余定理其实思想和拉格朗日插值的函数构造思路差不多，正好之前学了中国剩余定理但没搞太明白，所以现在来稍微复习一波。

这个东西最开始来自《孙子算经》：

今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？

说人话就是求解以下这一个同余方程组：

$$\begin{array}{} x \equiv 2\ (mod\ 3) \\ x \equiv 3\ (mod\ 5) \\ x \equiv 2\ (mod\ 7)\end{array}$$

我们可以设 $x =a+b+c$ 且满足：

$$a \equiv 2 \ (mod\ 3),a \equiv 0 \ (mod\ 5),a \equiv 0 \ (mod\ 7)$$
$$b \equiv 0 \ (mod\ 3),b \equiv 3 \ (mod\ 5),b \equiv 0 \ (mod\ 7)$$
$$c \equiv 0 \ (mod\ 3),c \equiv 0 \ (mod\ 5),c \equiv 2 \ (mod\ 7)$$

正确性显然

辣么我们现在所需要做的就是找到 $a,b,c$ 啦

这样应该就比较显然了，我们单看求其中一个，其他做法一样，那就看 $a$ 好了

我们可以首先求出一个数字 $k$ 满足 ：

$$\begin{array}{} k \equiv 1\ (mod\ 3) \\ k \equiv 0\ (mod\ 5) \\ k \equiv 0\ (mod\ 7)\end{array}$$

则 $a = k \times 2$ 即可

再乱搞一下就是：
$$\begin{array}{} k \equiv 1\ (mod\ 3) \\ k \equiv 0\ (mod\ 35) \end{array}$$
$$(35=lcm(5,7))$$

首先显然 $k$ 是 $35$ 的倍数，并且 $\% 3$ 余 $1$。

有一个数字可以完美解决......那不就是 $35$ 乘上 $35$ 在模 $3$ 意义下的逆元嘛！！！

于是我们就只需要求逆元即可......

这里我们就能看出，所有的模数 必须两两互质 ！！！

因此，我们就得出了这样一个东西：

解方程

$$\begin{array}{} x \equiv a_1\ (mod\ m_1) \\ x \equiv a_2\ (mod\ m_2) \\ ...\\ x \equiv a_n\ (mod\ m_n)\end{array}$$

条件是：$\forall\ i \ne j,gcd(m_i,m_j)=1$

我们令 $M = \prod_{i=1}^n m_i\ ,\ M_i=\dfrac{M}{m_i}$，同时 $M_i^{-1}$ 为 $M_i$ 在模 $m_i$ 意义下的逆元

那么我们就可以得到一个解:

$$x=\sum_{i=1}^n a_i\times M_i \times M_i^{-1}$$

最小正整数解呢？显然就是 $x \ \% \ {lcm}_{i=1}^n m_i$

大功告成啦！

板子 P1495 【模板】中国剩余定理(CRT)/曹冲养猪

//Code By CXY
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int MAXN = 21;

int n,ans;
int a[MAXN],m[MAXN],M = 1;

void ExGcd(int a,int b,int &x,int &y) {
    if(!b) {
        x = 1,y = 0;
        return;
    }
    ExGcd(b,a % b,y,x);
    y -= a / b * x;
}

signed main () {
    scanf("%lld",&n);
    for(register int i = 1;i <= n; ++i) {
        scanf("%lld%lld",&m[i],&a[i]);
        M *= m[i];
    }
    for(register int i = 1,Mi,x,y;i <= n; ++i) {
        Mi = M / m[i];
        ExGcd(Mi,m[i],x,y);
        (ans += a[i] * Mi * x) %= M;
    }
    printf("%lld\n",(ans % M + M) % M);
    return 0;
}

例题

UVA756 Biorhythms

题意：

多组数据，每次给 $p,e,i,d$，求最小的 $x$ 满足：$x > d$ 且

$$\begin{array}{} x \equiv p\ (mod\ 23) \\ x \equiv e\ (mod\ 28) \\ x \equiv i\ (mod\ 33)\end{array}$$

发现三个模数两两互质，直接上中国剩余定理即可

由于这里的模数是固定的，所以我们完全可以预处理之前的 $M,M_i,M_i^{-1}$，从而做到单次询问 $O(1)$ 回答，代码就不贴了 很久之前写的 很丑

扩展中国剩余定理 (ExCRT)

这东西嘛，说是叫扩中，但其实跟中国剩余定理没半毛钱关系

它是用来求解

$$\begin{array}{} x \equiv a_1\ (mod\ m_1) \\ x \equiv a_2\ (mod\ m_2) \\ ...\\ x \equiv a_n\ (mod\ m_n)\end{array}$$

这样的同余方程组的一种算法

和 $CRT$ 很像对吧，只是它没有那个 $"\forall\ i \ne j,gcd(m_i,m_j)=1"$ 的条件了

那要怎么做呢？

假设我们现在已经求得一个解 $x$，它已经满足前 $k-1$ 个方程了，那如何使这个解满足第 $k$ 个方程组呢？

首先我们设 $M = lcm_{i=1}^{k-1} m_i$，那么前 $k-1$ 个方程的通解为：

$$x + i \times M (i \in \mathbb{Z})$$

现在我们需要找到一个整数 $s$，使得：

$$x + s \times M \equiv a_k(mod\ m_k)$$

我们就解决了上面那个问题了

怎么求呢？我们可以 魔改 挪一下这个柿子，变成：

$$s \times M \equiv a_k - x (mod \ m_k)$$

这东西好眼熟啊，不是 $Exgcd$ 求的东西嘛！！

并且如果某一个方程无解，那显然整个方程组都是无解的啦

那我们就做完啦！只要多次做 $Exgcd$ 即可

板子 P4777 【模板】扩展中国剩余定理（EXCRT）

$ps:$ 这题输入有点毒瘤，稍微改一下就好

为了防止爆 $long\ long$ ，还要写一个 龟速乘 快速乘，其实跟快速幂差不多

//Code By CXY
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int MAXN = 1e5 + 10;

int n,x,y;
int a[MAXN],b[MAXN];
int M,ans;

inline int mul(int a,int b,int mod) {
    int res = 0;
    while(b) {
        if(b & 1) (res += a) %= mod;
        (a *= 2) %= mod;
        b >>= 1;
    }
    return res;
}

int Exgcd(int a,int b,int &x,int &y) {
    if(!b) {
        x = 1,y = 0;
        return a;
    }
    int tmp = Exgcd(b,a % b,y,x);
    y -= (a / b) * x;
    return tmp;
}

int ExCRT () {
    M = b[1],ans = a[1];
    for(register int i = 2;i <= n; ++i) {
        int a1 = M,b1 = b[i],c1 = ((a[i] - ans) % b[i] + b[i]) % b[i];
        int gcd = Exgcd(a1,b1,x,y);
        if(c1 % gcd) return -1;
        x = mul(x,c1 / gcd,b1 / gcd);
        ans += x * M;
        M *= b1 / gcd;
        ((ans %= M) += M) %= M;
    }
    return ans;
}

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

例题不想找也不想写了，咕了算了