中国剩余定理即解一组带余除法的不定方程组(同余式组解法)。
例如:求一个最小数x,已知x%3=2且x%5=3且x%7=2。
思路就是:
1、先从(3,5)的公倍数中找一个%7=1的最小公倍数,这里是15;再从(3,7)的公倍数中找一个%5=1的最小公倍数,这里是21;再从(5,7)的倍数中找一个%3=1,这里是70。
2、用A=15*2=30,并且30%7=2;用B=21*3=63,并且63%5=3;用C=70*2=140,并且140%3=2;
3、然后把这三个数相加:30+63+140=233;
4、用233 去除以(3,5,7)的最小公倍数105,得到余数23,即233%105=23, 23就是符合条件的最小X。
思路分析:
1、首先提及一个数学公式 a%b=c则 (a+K*b)%b=c;
2、上述的A是(3,5)的公倍数,B是(3,7)的公倍数,C是(5,7)的公倍数。A满足A%7=2,通过上面的公式可得(A+B+C)%7=2,因为B,C都是7的倍数;同理(A+B+C)%5=3,(A+B+C)%3=2。
3、A+B+C一定满足题目的要求,但不是最小的,所以最后结果我们只需要从A+B+C 中最大限度的减掉(3,5,7)的最小公倍数,即(A+B+C)%105=23;
对于poj1006这个题。
题意:
告诉你有三个值, physical, emotional, 和 intellectual ,它们周期分别为23,28,33。
题目给你这个三个值到达峰值的天数分别为p,e,i,也告诉的时间已经去过d天,问这个三个值同时到达峰值至少还需要多少天?
设还需要X天:
则X%23=p;X%28=e;X%33=i;同上解析
A=28*33*K*p (28*33*K%23==1)=5544*p;
B=23*33*K*e (23*33*K%28==1 ) =14421*e;
C=28*23*K*i (28*23*K%33==1)=1288*i;
代码如下:
#include<stdio.h>
#include<algorithm>
#include<iostream>
#define N 21252
using namespace std;
int p,e,i,d;
int main()
{
int t=0;
while(~scanf("%d%d%d%d",&p,&e,&i,&d))
{
if(p==-1&&e==-1&&i==-1&&d==-1)
break;
t++;
int num=0;
num=5544*p+14421*e+1288*i;
num=(num-d+N)%N;
if(num==0)
num=N;
printf("Case %d: the next triple peak occurs in %d days.\n",t,num);
}
return 0;
}