【題目來源】
https://www.luogu.com.cn/problem/P1495
https://www.acwing.com/problem/content/225/
【題目描述】
自從曹沖搞定了大象以后，曹操就開始捉摸讓兒子干些事業，于是派他到中原養豬場養豬。可是曹沖滿不高興，于是在工作中馬馬虎虎。有一次曹操想知道母豬的數量，于是曹沖想狠狠耍曹操一把。舉個例子，假如有 16 頭母豬，如果建了 3 個豬圈，剩下 1 頭豬就沒有地方安家了。如果建造了 5 個豬圈，但是仍然有 1 頭豬沒有地方去，然后如果建造了 7 個豬圈，還有 2 頭沒有地方去。你作為曹操的私人秘書理所當然要將準確的豬數報給曹操，你該怎么辦？
【輸入格式】
第一行包含一個整數n：建立豬圈的次數。
接下來n行，每行兩個整數ai、bi，表示建立了ai個豬圈，有bi頭豬沒有去處。你可以假定a1~an互質。
【輸出格式】
輸出包含一個正整數，即為曹沖至少養母豬的數目。
【輸入樣例】
3
3 1
5 1
7 2
【輸出樣例】
16
【說明/提示】
1≤n≤10，
0≤bi＜ai≤100000，
1≤∏ai≤10^18
【算法分析】
● 中國剩余定理應用的充要條件是模數互質（在本題中也就是豬圈數目互質）。
● 中國剩余定理算法步驟
（1）計算模數的乘積：M=m1·m2·…·mk
（2）對每個模數 mi，計算 Mi=M/mi
（3）對每個 Mi，求解 Mi 在模 mi 下的逆元 yi，即滿足 Mi·yi≡1(mod mi)
（4）最終解 x 為：x=∑ai·Mi·yi(mod M)，i∈(1,k)
其中，ai 是每個同余方程的余數。
●?中國剩余定理應用示例
例題：給定同余方程組： x≡2(mod 3)，x≡3(mod 5)，x≡2(mod 7) 由于模數 3、5、7 互質，所以可以采用中國剩余定理求解。步驟如下：
（1）計算 M=3×5×7=105。
（2）計算每個 Mi：M1=105/3=35，M2=105/5=21，M3=105/7=15。
（3）計算每個逆元 yi： 對于 M1=35，求解 35·y1≡1(mod 3)，得到 y1=2。 對于 M2=21，求解 21·y2≡1(mod 5)，得到 y2=1。 對于 M3=15，求解 15·y3≡1(mod 7)，得到 y3=1。
（4）求解 x： x=(2×35×2+3×21×1+2×15×1) mod 105 =233 mod 105=23。
【算法代碼】
#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int N=15;
LL m[N],a[N];LL exgcd(LL a,LL b,LL &x,LL &y) {if(b==0) {x=1,y=0;return a;}LL d=exgcd(b,a%b,y,x);y-=(a/b)*x;return d;
}int main() {int n;cin>>n;LL M=1;for(int i=1; i<=n; i++) {cin>>m[i]>>a[i];M*=m[i];}LL t=0;for(int i=1; i<=n; i++) {LL x,y;LL Mi=M/m[i];exgcd(Mi,m[i],x,y);t=(t+a[i]*Mi%M*x)%M;}t=(t+M)%M;cout<<t<<endl;return 0;
}/*
in:
3
99991 99990
99989 99988
99971 99970out:
282926331270118
*/
【參考文獻】
https://www.luogu.com.cn/problem/P1495
https://www.luogu.com.cn/problem/P4777
https://www.acwing.com/problem/content/206/
https://blog.csdn.net/qq_33127317/article/details/108439841
https://www.luogu.com.cn/problem/solution/P1495
https://blog.csdn.net/qq_51352378/article/details/123491047
https://www.acwing.com/solution/content/148128/
https://www.acwing.com/solution/content/164120/
)
