有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?
三人同行七十稀,五树梅花廿一支,七子团圆正半月,除百零五使得知
——《孙子算经》
它可以做什么?
中国剩余定理可以用于解决形如以下形式的线性同余方程组
其中(m_1,m_2,m_3,ldots,m_n)两两互质
它是怎么做的?
中国剩余定理利用构造法给出了一组解,构造方法如下:
设(M=prod_{i=1}^nm_i),并设(M_i=M/m_i),即(M_i=prod_{j=1,j
eq i}^nm_j)
设(t_i=M_i^{-1})为(M_i)模(m_i)意义下的逆元,那么同余方程组((X))的通解可以表示为以下形式:
在模(M)意义下,方程组的解为:
为什么是正确的?
证明如下:
由于(m_1,m_2,m_3,ldots,m_n)两两互质,因此有(gcd(M_i,m_i)=1),所以存在(t_i)满足(M_it_i=1pmod{m_i})
于是有:(b_iM_it_iequiv b_i*1equiv b_ipmod {m_i})
且对于(forall jin{1,2,3,ldots,n},j eq i),有(b_iM_it_iequiv0pmod{m_j})
那么对于(forall iin{1,2,3,ldots,n}),(x=sum_{i=1}^nb_iM_it_i)满足:
由此可以证明(x)是同余方程组((X))的一个解
另外,若(x_1,x_2)都是方程组((X))的解,那么
对于(forall iin{1,2,3,ldots,n},x_1-x_2equiv0pmod{m_i})
而(m_1,m_2,m_3,ldots,m_n)两两互质,所以(M|(x_1-x_2)),这说明方程组((X))的任意两个解之间相差(kM,kinmathbb{Z})
那么方程组的所有整数解的形式即为:
Code
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#define maxn 105
using namespace std;
int n;
int b[maxn],m[maxn],lcm=1,M[maxn],t[maxn];
int exgcd(int a,int p,int &x,int &y)
{
if(!p)
{
x=1;
y=0;
return a;
}
int xx,yy,k;
k=exgcd(p,a%p,xx,yy);
x=yy;
y=xx-a/p*yy;
return k;
}
int main()
{
int ans=0;
scanf("%d",&n);
register int i;
for(i=1;i<=n;++i)
{
scanf("%d%d",&b[i],&m[i]);
lcm*=m[i];
}
for(i=1;i<=n;++i)
{
int x,y;
M[i]=lcm/m[i];
exgcd(M[i],m[i],x,y);
ans=(ans+b[i]*M[i]*x)%lcm;
}
printf("%d",ans);
return 0;
}
例题
UVA756 Biorhythms
Description
输入包含若干个测试点,以四个 (-1) 结束。
每一个测试点输入四个整数 (p), (e), (i) 和 (d)。求最小的 (x),使得 (x>d) 并且
输出(x-d)的值
输出请按照如下格式:
Case 1: the next triple peak occurs in 1234 days.
Solution
中国剩余定理裸题,直接套用即可
Code
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdlib>
using namespace std;
typedef long long ll;
int b[4],m[4]={0,23,28,33},M[4]={0,924,759,644},t[4];
int lcm=21252;//23*28*33
void exgcd(int a,int b,int &x,int &y)
{
if(!b)
{
x=1,y=0;
return;
}
exgcd(b,a%b,y,x);
y-=a/b*x;
}
void Pre()
{
int y;
for(int i=1;i<=3;++i)
{
exgcd(M[i],m[i],t[i],y);
t[i]=(t[i]+m[i])%m[i];
}
}
int main()
{
Pre();
int cas=0,d;
while(1)
{
for(int i=1;i<=3;++i)
scanf("%d",&b[i]);
scanf("%d",&d);
if(b[1]==-1)
break;
int ans=0;
for(int i=1;i<=3;++i)
ans=(ans+b[i]*M[i]*t[i]%lcm)%lcm;
ans=(ans-d+lcm)%lcm;
if(ans==0)
ans=lcm;
printf("Case %d: the next triple peak occurs in %d days.
",++cas,ans);
}
return 0;
}
部分内容来源:
孙子定理_百度百科
《信息学奥赛之数学一本通》林厚从 著