中国剩余定理poj1006

中国剩余定理即解一组带余除法的不定方程组(同余式组解法)。

例如:求一个最小数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;
}

上一篇:Python中星号的本质和使用方式


下一篇:tcp socket/ unix socket