信息学奥赛一本通 1634：【例 4】曹冲养猪 | 洛谷 P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪
【题目链接】
ybt 1634：【例 4】曹冲养猪
洛谷 P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪
【题目考点】
1. 中国剩余定理
有线性同余方程组：
{ x ≡ a 1 ( m o d m 1 ) x ≡ a 2 ( m o d m 2 ) ⋮ x ≡ a n ( m o d m n ) \begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_n \pmod{m_n} \end{cases}⎩⎨⎧x≡a1(modm1)x≡a2(modm2)⋮x≡an(modmn)
其中m 1 , m 2 , . . . , m n m_1, m_2, ..., m_nm1,m2,...,mn互质。
中国剩余定理可以求解以上线性同余方程组。
设M = m 1 m 2 . . . m n M=m_1m_2...m_nM=m1m2...mn，为m 1 m_1m1到m n m_nmn的乘积。
设q i = M m i q_i=\dfrac{M}{m_i}qi=miM。
线性同余方程组的解为
x = ∑ i = 1 n a i q i ( q i − 1 m o d m i ) x=\sum_{i=1}^na_iq_i(q_i^{-1} \bmod m_i)x=i=1∑naiqi(qi−1modmi)
证明：
对于任一同余方程x ≡ a k ( m o d m k ) x\equiv a_k \pmod{m_k}x≡ak(modmk)
求∑ i = 1 n a i q i ( q i − 1 m o d m i ) m o d m k \sum_{i=1}^na_iq_i(q_i^{-1} \bmod m_i)\bmod m_k∑i=1naiqi(qi−1modmi)modmk
- 当i ≠ k i\neq ki=k时，由于m k ∣ M m_k\mid Mmk∣M，且g c d ( m k , m i ) = 1 gcd(m_k, m_i)=1gcd(mk,mi)=1，所以m k ∣ M m i m_k\mid \frac{M}{m_i}mk∣miM，即m k ∣ q i m_k\mid q_imk∣qi。
所以a i q i ( q i − 1 m o d m i ) m o d m k = 0 a_iq_i(q_i^{-1} \bmod m_i)\bmod m_k = 0aiqi(qi−1modmi)modmk=0 - 当i = k i=ki=k时，a k q k ( q k − 1 m o d m i ) m o d m k = a k m o d m k a_kq_k(q_k^{-1} \bmod m_i)\bmod m_k=a_k\bmod m_kakqk(qk−1modmi)modmk=akmodmk
所以∑ i = 1 n a i q i ( q i − 1 m o d m i ) m o d m k = a k m o d m k \sum_{i=1}^na_iq_i(q_i^{-1} \bmod m_i)\bmod m_k=a_k\bmod m_k∑i=1naiqi(qi−1modmi)modmk=akmodmk
即当x = ∑ i = 1 n a i q i ( q i − 1 m o d m i ) x=\sum_{i=1}^na_iq_i(q_i^{-1} \bmod m_i)x=∑i=1naiqi(qi−1modmi)时满足x ≡ a k ( m o d m k ) x\equiv a_k \pmod{m_k}x≡ak(modmk)
因此x = ∑ i = 1 n a i q i ( q i − 1 m o d m i ) x=\sum_{i=1}^na_iq_i(q_i^{-1} \bmod m_i)x=∑i=1naiqi(qi−1modmi)满足该线性同余方程组。
2. 乘法逆元
乘法逆元相关知识见：洛谷 P1082 [NOIP 2012 提高组] 同余方程
【解题思路】
设共有x xx头猪，建a i a_iai个猪圈，b i b_ibi头猪没有去处，那么满足x m o d a i = b i x\bmod a_i = b_ixmodai=bi，写成同余方程，为x ≡ b i ( m o d a i ) x\equiv b_i \pmod{a_i}x≡bi(modai)。
那么本题需要求该同余方程组的解
{ x ≡ b 1 ( m o d a 1 ) x ≡ b 2 ( m o d a 2 ) ⋮ x ≡ b n ( m o d a n ) \begin{cases} x \equiv b_1 \pmod{a_1} \\ x \equiv b_2 \pmod{a_2} \\ \vdots \\ x \equiv b_n \pmod{a_n} \end{cases}⎩⎨⎧x≡b1(moda1)x≡b2(moda2)⋮x≡bn(modan)
可以使用中国剩余定理求解。
注意，在求解过程中表达式的值可能会超出long long类型的表示范围，应该将表达式的值强转为__int128类型（128位整型），完成计算。
【题解代码】
解法1：中国剩余定理
#include<bits/stdc++.h>usingnamespacestd;#defineN15#defineMOD(a,b)(((a)%(b)+(b))%(b))//数学取模 a mod btypedeflonglongLL;voidexgcd(LL a,LL b,LL&x,LL&y)//扩展欧几里得定理{if(b==0){x=1,y=0;return;}exgcd(b,a%b,y,x);y-=a/b*x;}LLinv(LL a,LL m)//求a模m的逆元{LL x,y;exgcd(a,m,x,y);returnMOD(x,m);}LLCRT(LL*a,LL*m,LL n)//x≡a[i] (mod m[i]) i:[1, n]{LL M=1,res=0;for(inti=1;i<=n;++i)M*=m[i];for(inti=1;i<=n;++i)res=(res+(__int128_t)a[i]*M/m[i]*inv(M/m[i],m[i]))%M;returnres;}intmain(){LL n,a[N],b[N];cin>>n;for(inti=1;i<=n;++i)cin>>a[i]>>b[i];cout<<CRT(b,a,n);return0;}