約定
- \(A\perp B\) 表示 \(\gcd(A,B)=1\)，
- \(A\mid B\) 表示 \(B\equiv 0\pmod{A}(A\neq0)\)，
引入
考慮以下這道題：
有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二， 問物幾何？—— 《孫子算經》
也就是說，求出下列關于 \(x\) 方程組的最小整數解：
\[\begin{cases} x\equiv2\pmod{3}\\ x\equiv3\pmod{5}\\ x\equiv2\pmod{7} \end{cases} \]決議
首先我們考慮什么時候 \(\equiv3\pmod{3}\)，什么時候 \(\equiv3\pmod{5}\)，什么時候 \(\equiv2\pmod{7}\)，也就是解下面的方程：
\[\begin{cases} x_1\equiv2\pmod{3}\\ x_2\equiv3\pmod{5}\\ x_3\equiv2\pmod{7} \end{cases} \]解得：
\[\begin{cases} x_1=3k_1+2&(k_1\in\mathbb{Z})\\ x_2=5k_2+3&(k_2\in\mathbb{Z})\\ x_3=7k_3+2&(k_3\in\mathbb{Z})\\ \end{cases} \]但這個解毫無用處，因為我們無法直接從 \(x_1,x_2,x_3\) 求出 \(x\)，
一種常見的想法是，取 \(x=x_1+x_2+x_3\)，那我們就有結論 \(x_1+x_2\equiv2\pmod{3}\)，
這個結論顯然只在 \(3\mid x_2\) 時成立，
因此我們可以得到，令 \(x_1=(5\cdot7)y_1,x_2=(3\cdot7)y_2,x_3=(3\cdot5)y_3\)，則：
\[\begin{cases} 35y_1\equiv2\pmod{3}\\ 21y_2\equiv3\pmod{5}\\ 15y_3\equiv2\pmod{7} \end{cases} \]然后發現 \(\equiv\) 右邊的數字不是 \(1\) 就非常煩，我們令 \(z_1=2y_1,z_2=3y_2,z_3=2y_3\)，再分別約去 \(2,3,2\) 得到：
\[\begin{cases} 35z_1\equiv1\pmod{3}\\ 21z_2\equiv1\pmod{5}\\ 15z_3\equiv1\pmod{7} \end{cases} \]注意到 \(3\perp5\perp7\)，則 \(35\perp3,21\perp5,15\perp7\)，所以存在逆元（存在 \(z_1,z_2,z_3\)），這個可以用擴展歐幾里得或者線性求逆元來求出 \(z_1=2,z_2=1,z_3=1\)，
則 \(y_1=4,y_2=3,y_3=2\)，\(x_1=140,x_2,=63,x_3=30\)，則 \(x=233\)，
但是 \(233\) 并不是最小正整數解，不難發現只要 \(a\equiv b\pmod{3\cdot5\cdot7}\)，那么 \(a,b\) 都是合法解，
所以最小正整數解是 \(233\bmod (3\cdot5\cdot7)=23\)，
整理
現在，我們就得到了求解下列方程組的通法：
\[\begin{cases} x\equiv b_1\pmod{a_1}\\ x\equiv b_2\pmod{a_2}\\ \cdots\cdots\cdots\cdots\cdots\cdot\cdot\\ x\equiv b_n\pmod{a_n}\\ \end{cases} \]其中 \(a_1\perp a_2\perp\cdots a_n\)，
-
求出 \(K=\prod_{i=1}^{n}a_i\)，
-
對于 \(1 \leq i \leq n\)，解關于 \(z_i\) 的方程 \(\dfrac{K}{a_i}\cdot z_i\equiv1\pmod{a_i}\)，
-
計算 \(y_i=b_i\cdot z_i \cdot \dfrac{K}{a_i}\)，
-
則最小整數解 \(x=\sum_{i=1}^{n}{y_i} \bmod K\)，
例題
P1495 【模板】中國剩余定理（CRT）/ 曹沖養豬
給出兩個長為 \(n\) 的序列 \(a,b\)，求以下關于 \(x\) 的方程組的最小整數解：
\[\begin{cases} x\equiv b_1\pmod{a_1}\\ x\equiv b_2\pmod{a_2}\\ \cdots\cdots\cdots\cdots\cdots\cdot\cdot\\ x\equiv b_n\pmod{a_n}\\ \end{cases} \]\(1 \leq n \leq 10\)
模板題，大家可以參考一下我的代碼實作：
#include <bits/stdc++.h>
#define int long long
using namespace std;
void exgcd(int a,int b,int &x,int &y){
if(b==0){
x=1;
y=0;
}
else{
exgcd(b,a%b,x,y);
int tmp=x;
x=y;
y=tmp-a/b*y;
}
}
int n,a[15],b[15];
signed main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
int K=1,x=0;
for(int i=1;i<=n;i++) K*=a[i];
for(int i=1;i<=n;i++){
int z=0,ytxy=0,y=0;
exgcd(K/a[i],a[i],z,ytxy);
z=((z%a[i]+a[i])%a[i]);
y=b[i]*z*(K/a[i]);
x+=y;
}
cout<<((x%K+K)%K);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/551502.html
標籤：其他
上一篇：Codeforces Round 868 Div 2
下一篇：返回列表