当前位置：首页 > news >正文

【提高+/省选−】洛谷P1495 —— 【模板】中国剩余定理（CRT）/ 曹冲养猪

news 来源：原创 2025/7/27 20:50:41

见：P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪 - 洛谷

题目描述

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

输入格式

第一行包含一个整数 n —— 建立猪圈的次数，接下来 n 行，每行两个整数 ai,bi，表示建立了 ai 个猪圈，有 bi 头猪没有去处。你可以假定 a1∼an 互质。

输出格式

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

输入输出样例

in：
3
3 1
5 1
7 2
out：
16

说明/提示

1≤n≤10，0≤bi<ai≤100000，1≤∏ai≤1018

中国剩余定理（CRT）

不难看出，

题面可以翻译为：

Q：求解以下线性同余方程组：

⎩⎨⎧x≡r1(modm1)x≡r2(modm2)...x≡rn(modmn)

其中模数 m1.m2,...

mn 为 两两互质 的整数，

求 x 的最小非负整数解。

利用中国剩余定理求解，步骤如下：

(1) 计算所有模数的积 M=∏i=1nmi；

(2) 计算 ci=miM；

(3) 计算 ci 在模 mi 意义下的乘法逆元 ci−1；

(4) 计算解 x=∑i=1nricici−1(modM).
中国剩余定理的证明：
- 首先证明 x=∑i=1nricici−1 对于每一个 j 都有 x≡rj(modmj).
  - 若 i=j ，则 cj 中包含因数 ci，
    ∴cj≡0(modmj),
    ∴rjcjcj−1≡0(modmj).
  - 若 i=j ，则 cj 中不包含因数 ci，
    ∴cj≡0(modmi),
    ∵cjcj−1≡1(modmj).
    ∴rjcjcj−1≡rj(modmj).
  则对于 j ，总有：
  
  x≡i=1∑nricici−1(modmj)≡rjcjcj−1(modmj)≡rj(modmj)
- 其次，证明 x=∑i=1nricici−1 (mod M) 对于每一个 j 都有 x≡rj (mod mj).
  
  对于每一个 mj 来说，mod M 相当于减去 mj 的若干倍，
- 不会影响余数 rj 的结果.
证毕.
中国剩余定理的算法实现：

对于 M 和 ci，可以在两次循环时分别计算；

对于 ci−1，
可以转化为利用 扩展欧几里得算法 求解：
- 给定两个互质整数 a,m，对于 ax≡1 (mod m).，求 a 的乘法逆元 x (0<x<m).
  
  把同余方程转化为不定方程.
  由 ax≡1 (mod m)
  得 ax=m×(−y)+1 （设为 −y 便于移项后计算）
  得 ax+my=1.
  转化为用 扩欧求解不定方程 求 ax+my=1=gcd(a,m) 方程中 x 的解.
  
  为确保得到的答案为 最小正整数 ，最后答案为 (x%m+m)%m.
  e.g. x=−7,m=5,ans=(−7%5+5)%5=3;
  x=7,m=5,ans=(7%5+5)%5=2.

作者提醒

我本来是用long long做的

但是有一个样例错了

后来发现数据量太大了

long long爆掉了

只能用__int128 才能通过。

核心代码：

#include <bits/stdc++.h>
using namespace std;
typedef __int128  ll;
const int q=3e6+5;
long long m[q],a[q];
ll e(ll a,ll b,ll &x,ll &y){if(b==0){x=1;y=0;return a;}ll d=e(b,a%b,y,x);y-=(a/b)*x;return d;
}int main() {long long n;cin>>n;ll g=1;for(int i=1;i<=n;i++){cin>>m[i]>>a[i];g*=m[i];}long long t=0;for(int i=1;i<=n;i++){ll x,y;ll mi=g/m[i];e(mi,m[i],x,y);t=(t+a[i]*mi%g*x)%g;}t=(t+g)%g;cout<<t;return 0;
}

各位大佬

鼓励一下

关注+收藏+点赞

好吗