企业官网建设流程全解析

【题目链接】

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​互质。
中国剩余定理可以求解以上线性同余方程组。

1. 设M = m 1 m 2 . . . m n M=m_1m_2...m_nM=m1​m2​...mn​，为m 1 m_1m1​到m n m_nmn​的乘积。

2. 设q i = M m i q_i=\dfrac{M}{m_i}qi​=mi​M​。

3. 线性同余方程组的解为
   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∑n​ai​qi​(qi−1​modmi​)

证明：
对于任一同余方程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=1n​ai​qi​(qi−1​modmi​)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​∣mi​M​，即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 = 0ai​qi​(qi−1​modmi​)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_kak​qk​(qk−1​modmi​)modmk​=ak​modmk​
  所以∑ 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=1n​ai​qi​(qi−1​modmi​)modmk​=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=1n​ai​qi​(qi−1​modmi​)时满足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=1n​ai​qi​(qi−1​modmi​)满足该线性同余方程组。

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;}