问题引入：
有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？《孙子算经》
就是计算一个数\(x\)满足\(\begin{cases} x≡2(MOD\ 3) \\ x≡3(MOD\ 5) \\ x≡2(MOD\ 7) \end{cases}\)
中国剩余定理：
首先对于同余方程，以下等式显然成立：
\]
接下来我们构造三个数\(a,b,c\)满足以下条件：
a\%3=2 & a\%5=0 & a\%7=0 \\
b\%3=0 & b\%5=3 & b\%7=0 \\
c\%3=0 & c\%5=0 & c\%7=2
\end{array} \right]\]
可以发现根据等式\(①\)，\(a+b+c\)即为所求\(x\)的一个解
现在考虑如何构造\(a,b,c\)三个数
首先\(a\)是\(5\)的倍数也是\(7\)的倍数，所以\(a\)是\(35\)的倍数，同理，\(b\)是\(21\)的倍数，\(c\)是\(15\)的倍数
所以令
a = 35\cdot k_a \\
b = 21\cdot k_b \\
c = 15\cdot k_c
\end{cases}\]
则
35\cdot k_a ≡ 2\ (MOD\ 3)\\
21\cdot k_b ≡ 3\ (MOD\ 5)\\
15\cdot k_c ≡ 2\ (MOD\ 7)
\end{cases}\]
设\(35\)在模\(3\)意义下的逆元为\(inv_a\)，\(21\)在模\(5\)意义下的逆元为\(inv_b\)，\(15\)在模\(7\)下的逆元为\(inv_c\)
\(inv_a = 2，inv_b = 1，inv_c = 1\)
则
k_a = 2\cdot inv_a = 4\\
k_b = 3\cdot inv_b = 3\\
k_c = 2\cdot inv_c = 2
\end{cases}
\]
所以：
a = 140\\
b = 63\\
c = 30
\end{cases}
\]
所以得到\(x\)的一个解\(x=a+b+c=233\)
如果要求得所有\(x\)中最小的非负整数解，只要用\(x\)对\(lcm(3,5,7)\)取模即可
所以最后得到的最小的\(x = 233\%(3\cdot 5\cdot 7)=23\)
推广到一般情况下：
\begin{cases}
x ≡ r_1\ (MOD\ p_1)\\
x ≡ r_2\ (MOD\ p_2)\\
\quad \quad \quad \vdots\\
x ≡ r_m\ (MOD\ p_m)\\
\end{cases}，其中\forall gcd(p_i,p_j)=1\]
\]
\]
例题：
HDU1370 Biorhythms 🔗
view code
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
typedef long long int LL;
const LL p[3] = {23,28,33};
void exgcd(LL a, LL b, LL &x, LL &y){
if(!b){ x = 1; y = 0; return; }
exgcd(b,a%b,y,x);
y -= a / b * x;
}
void solve(LL a[], LL d, int kase){
for(int i = 0; i < 3; i++) a[i] %= p[i];
LL P = p[0] * p[1] * p[2], sum = 0;
for(int i = 0; i < 3; i++){
LL inv, y;
exgcd(P/p[i],p[i],inv,y);
sum = (sum + P/p[i]*inv%P*a[i]%P) % P;
}
LL day = (sum%P+P)%P - d; if(day<=0) day += P;
printf("Case %d: the next triple peak occurs in %I64d days.\n",kase,day);
}
int main(){
int tt; ____();
for(cin >> tt; tt; tt--){
LL a[3], d;
int kase = 1;
while(cin >> a[0] >> a[1] >> a[2] >> d and (a[0]+a[1]+a[2]+d+4)) solve(a,d,kase++);
}
return 0;
}
扩展中国剩余定理
\begin{cases}
x ≡ r_1\ (MOD\ p_1) \\
x ≡ r_2\ (MOD\ p_2) \\
\quad \quad \quad \vdots \\
x ≡ r_m\ (MOD\ p_m)
\end{cases}
，\exists gcd(p_i,p_j)\ne 1
\]
首先考虑两个同余方程：
x ≡ r_1\ (MOD\ p_1) \\
x ≡ r_2\ (MOD\ p_2)
\end{cases}
，gcd(p_1,p_2)\ne 1
\]
可以得到：
\]
\]
根据裴蜀定理，\((r_2-r_1) \% gcd(p_1,p_2)\ne 0\)的情况下是无解的
在\((r_2-r_1) \% gcd(p_1,p_2) = 0\)的情况下，可以通过扩展欧几里得求得\(k_1\)和\(k_2\)
然后就可以得到：
\]
\]
\]
对于多个方程的情况下，两两合并即可
例题：
洛谷P4777🔗
view code
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
typedef long long int LL;
LL ksc(LL a, LL b, LL mod){
LL ret = 0;
int flag = ((a<0)^(b<0)) ? -1 : 1;
a = abs(a); b = abs(b);
while(b){
if(b&1) ret = (ret + a) % mod;
b >>= 1;
a = (a + a) % mod;
}
return ret * flag;
}
LL exgcd(LL a, LL b, LL &x, LL &y){
if(!b){ x = 1, y = 0; return a; }
LL g = exgcd(b,a%b,y,x);
y -= a/b*x;
return g;
}
pair<LL,LL> excrt(LL b1, LL p1, LL b2, LL p2){
LL d = b2 - b1, x, y;
LL g = exgcd(p1,p2,x,y);
LL p = p1 / g * p2;
x = ksc(x,d/g,p);
return make_pair(((ksc(x,p1,p)+b1)%p+p)%p,p);
}
int main(){
____();
int n;
LL b, p;
cin >> n >> p >> b;
for(int i = 1; i < n; i++){
LL bb, pp;
cin >> pp >> bb;
tie(b,p) = excrt(b,p,bb,pp);
}
cout << b << endl;
return 0;
}
原文链接: https://www.cnblogs.com/kikokiko/p/13199031.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/359742
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
