引入

看了洛谷的一些題解，很多引用了百度百科的一些官方求法，很復雜，雖然正確，但是對于初學者來說不是特別好懂。

于是寫一篇來介紹一下這個定理吧，概念更清晰一些。

在說中國剩余定理之前 首先先介紹 裴蜀定理

對于任意的正整數a,b,一定存在非零整數x,y，使得ax + by = gcd（a,b)

這里不做詳細證明，大家可以思考一下如何證明？

其實簡單來理解就是，因為a和b一定是最大公約數的倍數，所以a和b的倍數（非零整數倍）

也一定是最大公約數的倍數，那么我們只要讓這個倍數等于1，就能找到一組解x,y滿足上述方程；

那么對于上個式子，如何來求出解呢？

這里就用到了我們的擴展歐幾里得算法，如果大家不會的話，可以學習一下，或者我將在后面的博客中補充

---

題目

題目鏈接：洛谷P1495

題目的大意就是這幅圖 讓我們求出滿足方程的x的最小非負整數解

對于這樣的一個線性同余方程組 我們可以先考慮 假設只有兩個方程的方程組的情況

首先我們以這幅圖中第一個方程與第二個方程為例

那么可以知道

x = k1* a1 + m1;①

x = k2 * a2 + m2;②

我們假設k1，k2∈Z；

那么聯立兩個方程 就可以得到

k1 * a1 + m1 = k2 * a2 + m2;

移項 得

k1* a1 - k2 * a2 = m2 - m1;

乍一看 天哪 這不是和擴展歐幾里得算法中 求 ax + by = d的一組解一模一樣（d指的是 gcd(a,b)

這個方程有解情況的充要條件是 gcd（a1,a2) | (m2 - m1);

所以我們同樣可以用擴展歐幾里得算法 求出 k1 * a1 - k2* a2 = d的一組解k1,k2(注意這里的d不是指m2 - m1,

而是gcd(a1,a2);

可是原來的方程右側是m2-m1啊,不慌，認真思考下，a1與a2都是常數,我們只要變化k1，把它乘一個（m2-m1)/d不就可以了。

由此我們得到了該同余方程的一組解k1,k2

細心的我們還可以推出 這個方程k1的所有解應該是k1 = k1+k * （a2/d)

代入①式可以得到

x = k1*a1 + m1

= (k1+ k * (a2/d))a1 + m1

=a1k1+ m1 +k * (a1 * a2)/d

我們發現a1*a2/d事實上就是a1與a2的最小公倍數，可以把它記為a

那么上面這個式子就可以化簡為

x = a1k1 + m1 + k* a

又∵a1k1 +m1 事實上是我們方程組的一個解x

我們可以把它記為x0；

那么上面的式子就變成了 x = k * a + x0；發現了嗎，這個式子與我們前面的①式極為相似；

于是我們通過上面的計算 將兩個方程聯立后成功化簡成了一個方程，并且求出了一組k,a以及我們的解m(即為x）；

用上面的思路，每次將兩個方程合并為一個方程，更新我們的解，由于有n個方程，總共迭代n - 1次，最終得到我們的答案

注意，我們每次更新答案時，因為都要求出最小非負整數解，所以在不斷取模的時候要注意讓余數不能為負數，所以要取模加模再取模；

這樣我們就解決了這樣一道水題————

---

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
typedef long long LL;

LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(!b)
    {
       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 a1,m1;
    cin>>a1>>m1;
    bool flag = true;
    for(int i = 0; i < n - 1; ++ i)
    {
        LL a2,m2;
        cin>>a2>>m2;
        LL k1,k2;
        LL d = exgcd(a1,a2,k1,k2);//求一下右邊等式在最大公約數的條件下的一組解
        if((m2 - m1) % d)
        {
            flag = false;
            break;
        }//判斷是否有解
        k1 *= (m2 - m1)/d;
        LL t = a2/d;
        k1 = ((k1 % t) + t) % t;
        m1 = a1 * k1 +  m1;
        a1 =abs(a1 / d * a2);//依次更新我們的m1,k1，a1；這里最小公倍數我們默認為正數（實際上取負數也可以）
    }
    if(flag) 
    {
        cout<<((m1 % a1) +a1) % a1<<endl;//別忘了我們要最優解）
    }
    else puts("-1");
    return 0;
}

總結

以上是生活随笔為你收集整理的浅谈中国剩余定理的全部內容，希望文章能夠幫你解決所遇到的問題。

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