一、定义
中国剩余定理可以用来求解一些线性同余方程组：
[egin{cases}
xequiv a_1quad (mod quad m_1) \
xequiv a_2quad (mod quad m_2) \
...\
xequiv a_nquad (mod quad m_n) \
end{cases}
]
而前提条件是(m_1，m_2，...，m_n)之间两两互质。
二、求解方法
我们设(M=prod_{i=1}^{n}{m_i})。那么我们设(Mi=M/mi)，ti是线性同余方程(M_it_i≡1(mod quad m_i))的一个解
定理：对于线性同余方程组，解为(x=prod_{i=1}^{n}{a_iM_it_i})，并且在模(M)意义下有唯一解。
证明：(∵)Mi是除mi以为所有模数的倍数
(∴)对于(forall k≠i)，都有(a_iM_it_i≡0(mod quad m_k))
又(∵a_iM_it_i≡a_i(mod quad m_i))
(∴)代入(x)，原方程组成立，并且在模M意义下唯一。
因此我们只要用(exgcd)求出每个方程的解，在求和起来即可。
代码
void exgcd(int a,int b,int &g,int &x,int &y)
{
if(!b)g=a,x=1,y=0;
else exgcd(b,a%b,g,y,x),y-=a/b*x;
}
void IntChina(int a[],int m[],int n)
{
int M=1,res=0;
for(int i=1;i<=n;i++)
M*=m[i];
for(int i=1;i<=n;i++)
{
int Mi=M/m[i],g,x,y;
exgcd(Mi,m[i],g,x,y);
res=(res+x*a[i]*Mi)%M;
}
return (res+M)%M;
}
例1：Biorhythms
人的体力、情感和智力周期为23、28和33天，给出三个日期表示体力、情感和智力为峰值的日期，再给出一个初始日期，求从这一天开始，再过多少天三个峰值同时出现。
实际上就是让我们求解线性同余方程组的解:
[egin{cases}
x equiv a_1 quad (mod quad 23) \
x equiv a_2 quad (mod quad 28) \
x equiv a_3 quad (mod quad 33)
end{cases}
]
对于这个方程组，我们求出的解即为下一次三个都出现峰值得日期，减去初始日期即可。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll m[4]={0,23,28,33};
void exgcd(ll a,ll b,ll &g,ll &x,ll &y)
{
if(!b)g=a,x=1,y=0;
else exgcd(b,a%b,g,y,x),y-=a/b*x;
}
int main()
{
ll a[4],d,cas=0;
while(~scanf("%lld%lld%lld%lld",&a[1],&a[2],&a[3],&d))
{
if(a[1]==-1&&a[2]==-1&&a[3]==-1&&d==-1)break ;
ll M=21252,ans=0;
for(ll i=1;i<=3;i++)
{
ll mi=M/m[i];
ll g,x,y;
exgcd(mi,m[i],g,x,y);
ans=(ans+mi*x*a[i])%M;
}
ans=(ans-d+M)%M;
printf("Case %d: the next triple peak occurs in %d days.
",++cas,ans==0?M:ans);
}
}