中國剩余定理

??中國剩余定理又叫孫子定理。在《孫子算經》中有這樣一個問題：“今有物不知其數，三三數之剩二（除以3余2），五五數之剩三（除以5余3），七七數之 剩二（除以7余2），問物幾何？”這個問題稱為“孫子問題”，解決的孫子問題的一般解法就叫孫子定理又叫 天朝 中國剩余定理。
具體解法分兩步：
??1.找出3和5公倍數中除7余2的最小的數（30）、3和7公倍數中除5余3的最小的數（63）、5和7公倍數中除3余2的最小的數（140），然后將這三個數相加得233。（ps：為了簡化運算第一個數可以找 % 7 = 1的數之后在乘2，其他兩個數同理分別乘3、2。）
??而尋找取模后為1的數即為尋找其逆元，逆元的概念后面會說。
??2.用233除以3、5、7的最小公倍數105，得到余數23（即233%105 = 23），23即為所求。

是不是一臉懵（如果明明白白的請無視我這個菜雞），我第一次看也是想說就這么簡單？？？

但這是有數學依據的：

??設這三個數分別為n1、n2、n3。因為n1 % 7 == 2，n2、n3又都是7的倍數所以，(n1 + n2 + n3) % 7 == 2，其他兩個同理，所以最后得到的數233（n1+n2+n3）就滿足孫子問題中的三個條件，但這不一定是最小的解。

那么如何得到最小解？
??只需要在該解的基礎上最大限度的減去3、5、7的公倍數即可（即對該解取模233%105），為什么？因為這樣無論怎么減都不會影響其對于3、5、7的模數。

逆元

??給出 a 和 m ，一個數有逆元的充分必要條件是gcd(a,m)=1，此時逆元唯一存在，這時方程 ax ≡ 1（mod m）的最小整數解 x 稱為 a 模 m 的逆元。
??逆元的含義：
????在模m意義下，一個數a如果有逆元x，那么除以a相當于乘x。

??為什么要有乘法逆元呢？

????當我們要求（a/b） mod p的值，且a很大，大到會溢出；或者說b很大，達到會爆精度。無法直接求得a/b的值時，我們就要用到乘法逆元。

??那么如何求解逆元呢？
????根據上文我們知道ax ≡ 1（mod m）有解的條件是a和m互素，即gcd（a，m） == 1.

????易知ax mod m = ax - (ax / m) * m
????所以ax ≡ 1（mod m） 等價于 ax - (ax / m) * m = 1
????提出m得
??????ax + m( - ax / m) = 1
????令y = -（ax/m）得
??????ax + my = 1
????所以求解 ax ≡ 1（mod m）等價于求解 ax + my = 1 ,那么就可以用擴展歐幾里得定理求解。

擴展歐幾里得定理（exgcd）：

??給出整數a,b,n,求方程 ax + by = n 的所有整數解。有解的充分必要條件是gcd（a，b）可以整除 n 。簡單解釋如下：
????令 a = gce(a,b) * a’、 b = gcd(a,b) * b’ ， 則有 ax + by = gcd(a,b)(a’x + b’y) = n;如果 x 、y 、a’ 、b’都是整數，那么n必須是gcd(a,b)的倍數才有整數解。
??exgcd解出的 x 為 ax + by = gcd(a,b) 中的 x ，若要求 ax + by = n中的 x，兩邊還要乘上 n / gcd(a,b)。
??由歐幾里得算法，得

????ax+by=gcd(a,b)=gcd(b,a mod b)=bx′+(a mod b)y′

??代入上文的a mod b = a - ? a / b ? b 得
?????ax + by = bx’ + (a - ? a / b ? b) y’
????????= bx’ + ay’ - ? a / b ? by’
????????= ay’ + b(x’ - ? a / b ?y’)
????得 x = y′ , y = x′ ? ? a / b ?y′
??邊界情況分析，ax′+by′=gcd(a,b)，當 b=0 時，a 為 gcd(a,b)，當且僅當 x′=1時等式成立，y′ 可以為任意值，為方便起見，設y′=0，那么得到以下代碼：

void exgcd(int a,int b,int &x,int &y) {if(b==0){x=1;y=0;return;}exgcd(b,a%b,x,y);int z = x; x = y; y = z - (a/b)*y; }

求出的 x 即為 a 模 b 的逆元。

介紹完了看看這道例題：

luogu 曹沖養豬

題目描述
自從曹沖搞定了大象以后，曹操就開始捉摸讓兒子干些事業，于是派他到中原養豬場養豬，可是曹沖滿不高興，于是在工作中馬馬虎虎，有一次曹操想知道母豬的數量，于是曹沖想狠狠耍曹操一把。舉個例子，假如有 1616 頭母豬，如果建了 33 個豬圈，剩下 11 頭豬就沒有地方安家了。如果建造了 55 個豬圈，但是仍然有 11 頭豬沒有地方去，然后如果建造了 77 個豬圈，還有 22 頭沒有地方去。你作為曹總的私人秘書理所當然要將準確的豬數報給曹總，你該怎么辦？

輸入格式
第一行包含一個整數 n (建立豬圈的次數)，接下來 n 行，每行兩個整數 ai,bi， 表示建立了 ai個豬圈，有 bi 頭豬沒有去處。你可以假定 ai,aj互質。

輸出格式
輸出包含一個正整數，即為曹沖至少養母豬的數目。

輸入

3 3 1 5 1 7 2

輸出

16 #include<cstdio> #include<iostream> #include<cmath>#define ll long longusing namespace std;ll n,a[15],b[15],c[15],mul = 1,ans;void exgcd(ll a,ll b,ll &x, ll&y) {if(b == 0) {x = 1;y = 0;return;}exgcd(b,a%b,x,y);int z = x; x = y; y = z-y*(a/b); }int main( ) {scanf("%d",&n);for(int i = 1; i <= n; i++) {scanf("%d%d",&a[i],&b[i]);mul *= a[i];//求出所有數的最小公倍數（因為每個數都互質）}for(int i = 1; i <= n; i++) {c[i] = mul / a[i]; //除去a[i]所有數的最小公倍數ll x = 0, y = 0;exgcd(c[i],a[i],x,y);//求逆元ans += b[i] * c[i] * (x < 0 ? x + a[i]: x);//累加成其中一個解}printf("%lld",ans%mul);//輸出最小解return 0; }

兩年沒寫博客了，如有錯誤歡迎斧正。

總結

以上是生活随笔為你收集整理的中国剩余定理（孙子定理）+ exgcd求逆元的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。