中国剩余定理

小学数学时大家都学过这样的问题：

有一群人，三个人一组，剩1人，5个人一组，剩3人，十人一组，剩7人。

那么有多少人呢？

大家可以看成一个同余方程。

$$x \equiv 1(\mod 3)\\\ x \equiv 3(\mod 5)\\\ x \equiv 7(\mod 10)\\\ $$

枚举是一种办法，但是太慢了。

我们不妨看一下，把这个东西拆开。

定义一个$r$数组，表示如下关系：
$$r_1 \equiv 1(\mod 3), r_1 \equiv 0 (\mod 5), r_1 \equiv 0 (\mod 10)\\\ r_2 \equiv 0(\mod 3), r_2 \equiv 1(\mod 5), r_2 \equiv 0(\mod 10)\\\ r_3 \equiv 0(\mod 3), r_2 \equiv 0(\mod 5), r_3 \equiv 1(\mod 10)\\\ $$

那么我们发现，把$r$数组相加的结果就是答案。

此时我们定义一个$m$数组表示所有出了第i个数之外所有数乘起来。

那么$r[i]$应该就是模的数乘上$M[i]$再乘上$M[i]$的逆元。

逆元的话我们就直接用exgcd来求就行了。

来写一下板子题：曹冲养猪

自从曹冲搞定了大象以后，曹操就开始琢磨让儿子干些事业，于是派他到中原养猪场养猪，可是曹冲很不高兴，于是在工作中马马虎虎，有一次曹操想知道母猪的数量，于是曹冲想狠狠耍曹操一把。

举个例子，假如有 $16$ 头母猪，如果建了 $3$ 个猪圈，剩下 $1$ 头猪就没有地方安家了；如果建造了 $5$ 个猪圈，但是仍然有 $1$ 头猪没有地方去；如果建造了 $7$ 个猪圈，还有 $2$ 头没有地方去。

你作为曹总的私人秘书理所当然要将准确的猪数报给曹总，你该怎么办？

输入格式

第一行包含一个整数 $n$，表示建立猪圈的次数；

接下来 $n$ 行，每行两个整数 $a_i$,$b_i$，表示建立了 $a_i$ 个猪圈，有 $b_i$ 头猪没有去处。

你可以假定 $a_i$,$a_j$ 互质。

输出格式

输出仅包含一个正整数，即为曹冲至少养猪的数目。

数据范围

1≤n≤10,
1≤$b_i$≤$a_i$≤1100000

所有$a_i$的乘积不超过 $10^{18}$

输入样例：

3
3 1
5 1
7 2

输出样例：

16

就是板子题吗，我们先把exgcd的板子准备一下，用这个东西求逆元（虽然平常用qmi）

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

然后记得开longlong，不然会爆int。

最后奉上完整代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 10;
int n;
int A[N], B[N];
void exgcd(LL a, LL b, LL &x, LL &y)
{
    if(!b) 
    {
        x = 1, y = 0;
        return ;
    }
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}
int main()
{
    cin >> n;
    LL M= 1;
    for(int i = 0; i < n; i ++)
    {
        cin >> A[i] >> B[i];
        M *= A[i];
    }
    LL res= 0;
    for(int i = 0; i < n; i ++)
    {
        LL Mi = M / A[i];
        LL ti, x;
        exgcd(Mi, A[i], ti, x);
        res += B[i] * Mi * ti;
    }
    cout << (res % M + M) % M;
}

bye

别说我短qaq