曹冲养猪

扩展欧几里得求逆元 中国剩余定理 T3

P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

自从曹冲搞定了大象以后，曹操就开始捉摸让儿子干些事业，于是派他到中原养猪场养猪，可是曹冲满不高兴，于是在工作中马马虎虎，有一次曹操想知道母猪的数量，于是曹冲想狠狠耍曹操一把。举个例子，假如有 $16$ 头母猪，如果建了 $3$ 个猪圈，剩下 $1$ 头猪就没有地方安家了。如果建造了 $5$ 个猪圈，但是仍然有 $1$ 头猪没有地方去，然后如果建造了 $7$ 个猪圈，还有 $2$ 头没有地方去。你作为曹总的私人秘书理所当然要将准确的猪数报给曹总，你该怎么办？

输入格式

第一行包含一个整数 $n$ —— 建立猪圈的次数，接下来 $n$ 行，每行两个整数 $a_i,b_i$，表示建立了 $a_i$ 个猪圈，有 $b_i$ 头猪没有去处。你可以假定 $a_1\sim a_n$ 互质。

输出格式

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

样例 #1

样例输入 #1

3
3 1
5 1
7 2

样例输出 #1

16

提示

$1\le n\le 10$，$0\le b_i<a_i\le 100000$，$1\le \prod a_i\le 10^{18}$

思路

设原猪总数为 $x$, 当前分了 $b_i$ 个猪圈, 还剩下 $a_i$ 个牛, 可以把几个条件用同余方程组描述：

$$x\equiv a_i(\mathrm{mod}{b}_i)$$

而题目中又说 $b_i$ 之间是两两互质, 因此可以使用 中国剩余定理（CRT） 来直接解决。

定义 $M=b_1\times b_2\times \cdots \times b_n$, $t_i$ 为 $M$ 的逆元, 即 $t_i$ 满足 $t_i\times M\equiv 1(\mathrm{mod}{m}_i)$。 而对应的存在一个解 $x=\sum _{i=1}^n{a}_i{t}_i{m}_i$, 仅当 $b_i$ 互质时成立, 此式子为构造得出, 直接记忆就行。

此解也非最小正整数解, 有可能为负数, 需要进行取模 $(x\mathrm{mod}M+M)\mathrm{mod}M$ 。

另外求逆元还有基于费马小定理的快速幂求法, 但要求 $M$ 与 $b_i$ 互质, 这里不一定成立, 故还是用扩展欧几里得定理求出最小的 t。

代码

#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
 
const int N = 20;
LL a[N], b[N];
 
LL qmi(LL a, LL b, LL p)
{
    LL res = 1;
    while (b)
    {
        if (b & 1)
            res = (res * a) % p;
        a = (a * a) % p;
        b >>= 1;
    }
    return res;
}
 
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;
    return;
}
 
void solve()
{
    LL n;
    cin >> n;
 
    LL M = 1;
    for (int i = 0; i < n; i++)
    {
        cin >> b[i] >> a[i];
        M *= b[i];
    }
    LL res = 0;
    for (int i = 0; i < n; i++)
    {
        LL mi = M / b[i];
        LL t, x;
        exgcd(mi, b[i], t, x);
        res = (res + (a[i] * t * mi % M)) % M;
    }
    cout << (res % M + M) % M << endl;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}