POJ 1006 Biorhythms

悠悠 2022-09-05 13:55 90阅读 0赞

# 中国剩余定理 #

## 引子 ##

*  韩信点兵
 *  韩信命令士兵3人一排，结果多出2名；
 *  紧接着命令士兵5人一排，结果多出3名；
 *  他又命令士兵7人一排，结果又多出2名。
 *  韩信马上向将士们宣布“我军又1073名勇士”

--------------------

## 分析 ##

*  韩信怎么知道军队有1073名士兵呢？
 *  先列出除以3余2的数：

> 2 5 8 11 14 17 20 23 26

*  再列出除以5余3的数：

> 3 8 13 18 23 28

*  在这两列数中，首先出现的公众数是8,3与5的最小公倍数是15，两个合并成一个数就是：

> 8 + 15 \* n

*  将n分别去1,2,3，…即可得到数列：

> 8 23 38

*  再列出除以7余2的数：

> 2 9 16 23 30…

*  可以看出，符合题目条件的最小数是23。
 *  也就是说，我们已经把题目中三个条件合并成一个：该数除以105余23》
 *  由于汉军原有士兵1500人，死伤四五百人，即剩余的士兵应为1000余人，即可得到士兵的总数：

> 105 \* 10 + 23 = 1073

--------------------

*  或许还有点抽象？
 *  来看下一道 `小学数学`应用题
 *  有一个年级的同学,每9人一排多5人,每7人一排多1人, 每5人一排多2人,问这个年级至少有多少人?
 *  求数学高手详细解答!剩余定理是什么意思?
 *  5 和 9 的公倍数依次是 45、90、135、180、225 ……
 *  这些公倍数中，被7除余1的数是 225
 *  9 和 7 的公倍数依次是 63、126、189、252……
 *  这其中，被5除余2的是 252
 *  5 和 7 的公倍数是 35、70、105、140、……
 *  其中被9除余5的数是 140
 *  把以上 225 252 140 三个数相加，求得
 *  225 + 252 + 140 = 617
 *  5 7 9 三个数的最小公倍数是 5*7*9=315
 *  617-315 = 302
 *  因此 302 就是这个年级至少人数。

--------------------

## 余数的性质 ##

1.  余数小于除数
2.  a 为被除数，d 为除数，q 为商，r 为余数；

a=d*q+r;
    d=(a-r)/q;
    q=(a-r)/d;
    r=q-d*q;

1.  有自然数a,b,c，如果a,b除以c的余数相同，那么a与b的差能被c整除。
2.  a与b的和（a+b）除以c得到的余数（a，b两数除以c在没有余数的情况下除外），等于a，b分别除以c得到的余数之和（或这个和除以c的余数）。
3.  a与b的乘积除以c所得的余数，等于a，b分别除以c所得的余数之积（或这个积除以c的余数）。

## AC ##

#include <iostream>
    #include <algorithm>
    #include <cstdio>
    using namespace std;
    int main(){ 
    	int n1,n2,n3;
    	// 9 7 5
    	int y1,y2,y3;
    	// 5 1 2
    	cout<<"请输入3组数据，表示几人一排："<<endl; 
    	cin>>n1>>n2>>n3;
    	cout<<"请输入3组数据，表示余的人数："<<endl; 
    	cin>>y1>>y2>>y3;
    	int i,j,k,t,s;
    	//假设n1,n2,n3互质
    	int s1,s2,s3;
    	i=n1*n2;   //63
    	j=n2*n3;   //35
    	k=n1*n3;   //45
    	for(t=1;;t++){ 
    		if((t*i-y3)%n3==0){ 
    		    s1=t*i;
    		    break;
    	    } 
    	}
    	for(t=1;;t++){ 
    		if((t*k-y2)%n2==0){ 
    			s2=t*k;
    			break;
    		}
    	}
    	for(t=1;;t++){ 
    		if((t*j-y1)%n1==0){ 
    			s3=t*j;
    			break;
    		} 
    	}
    	//cout<<s1<<" "<<s2<<" "<<s3<<endl;
    	s=(s1+s2+s3)-(n1*n2*n3);
    	cout<<"这个年级至少人数:"<<endl<<s<<endl;
    	system("pause");
    	system("pause");
    	return 0;
    }

# Biorhythms #

*  Time Limit: 1000MS
 *  Memory Limit: 10000K
 *  Total Submissions: 160305
 *  Accepted: 52289

--------------------

## Description ##

Some people believe that there are three cycles in a person’s life that start the day he or she is born. These three cycles are the physical, emotional, and intellectual cycles, and they have periods of lengths 23, 28, and 33 days, respectively. There is one peak in each period of a cycle. At the peak of a cycle, a person performs at his or her best in the corresponding field (physical, emotional or mental). For example, if it is the mental curve, thought processes will be sharper and concentration will be easier.  
Since the three cycles have different periods, the peaks of the three cycles generally occur at different times. We would like to determine when a triple peak occurs (the peaks of all three cycles occur in the same day) for any person. For each cycle, you will be given the number of days from the beginning of the current year at which one of its peaks (not necessarily the first) occurs. You will also be given a date expressed as the number of days from the beginning of the current year. You task is to determine the number of days from the given date to the next triple peak. The given date is not counted. For example, if the given date is 10 and the next triple peak occurs on day 12, the answer is 2, not 3. If a triple peak occurs on the given date, you should give the number of days to the next occurrence of a triple peak.

--------------------

## Input ##

You will be given a number of cases. The input for each case consists of one line of four integers p, e, i, and d. The values p, e, and i are the number of days from the beginning of the current year at which the physical, emotional, and intellectual cycles peak, respectively. The value d is the given date and may be smaller than any of p, e, or i. All values are non-negative and at most 365, and you may assume that a triple peak will occur within 21252 days of the given date. The end of input is indicated by a line in which p = e = i = d = -1.

--------------------

## Output ##

> For each test case, print the case number followed by a message  
> indicating the number of days to the next triple peak, in the form:
> 
> Case 1: the next triple peak occurs in 1234 days.
> 
> Use the plural form \`\`days’’ even if the answer is 1.

--------------------

## Sample Input ##

0 0 0 0
    0 0 0 100
    5 20 34 325
    4 5 6 7
    283 102 23 320
    203 301 203 40
    -1 -1 -1 -1

--------------------

## Sample Output ##

Case 1: the next triple peak occurs in 21252 days.
    Case 2: the next triple peak occurs in 21152 days.
    Case 3: the next triple peak occurs in 19575 days.
    Case 4: the next triple peak occurs in 16994 days.
    Case 5: the next triple peak occurs in 8910 days.
    Case 6: the next triple peak occurs in 10789 days.

--------------------

## Source ##

*  East Central North America 1999

--------------------

## AC ##

#include <iostream>
    #include <algorithm>
    #include <cstdio>
    using namespace std;
    int main(){ 
    	long int n1,n2,n3,s;
    	// 23 28 33
    	int p,e,i,d;
    	int t,j=1;
    	for(;;j++){ 
    		cin>>p>>e>>i>>d;
    		if(p==-1&&e==-1&&i==-1&&d==-1)
    		    return 0;
    			for(t=1;;t++){ 
    				if(p%((t*28*33)%23)==0){ 
    				    n1=t*28*33*(p/((t*28*33)%23));
    				    break;
    			    }
    			}
    			for(t=1;;t++){ 
    				if(e%((t*23*33)%28)==0){ 
    					n2=t*23*33*(e/((t*23*33)%28));
    					break;
    				}
    			}
    			for(t=1;;t++){ 
    				if(i%((t*23*28)%33)==0){ 
    					n3=t*28*23*(i/((t*28*23)%33));
    					break;
    				}
    			}
    			s=(n1+n2+n3)%(23*28*33)-d;
    			while(s<=0){ 
    				s+=(23*28*33);
    			}
    			cout<<"Case "<<j<<": the next triple peak occurs in "<<s<<" days."<<endl;
    	}
    	return 0;
    }

--------------------