中国剩余定理的应用

偏执的太偏执、 2022-06-17 00:48 182阅读 0赞

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.

题意是在人的一生中有三种生物节律，身体、情绪和智力，每一个情绪都有相应的周期，到了这个周期点这个人的这个方面就变得特别屌。

现在给你这三个的周期为23 28 33。这是固定的了。

然后给你上一个三个周期的巅峰时刻是p e i，问从d时间开始还有多久的N天，三个周期一次一起到达巅峰。

列公式是N+d = p+23\*N1 = e+28\*N2 = i+33\*N3

N1,N2,N3是整数我们不用管，也没要求。要求的是N。

再转化一下就是求一个数最小的S，这个数S除以23余p，除以28余e，除以33余i。当然最后要求的那个N只需S-d就好了。

又一次涨姿势了。。。中国剩余定理。

首先求满足 除以23余1，整除28，整除33的三个条件的最小数，发现是5544。

然后求满足 除以28余1，整除23，整除33的三个条件的最小数，是14421。

然后求满足 除以33余1，整除23，整除28的三个条件的最小数，是1288。

然后5544\*p+14421\*e+1288\*i就一定是三个周期的下一个巅峰了，只不过不一定是最小值。

所以这三个相加就满足条件喽，只是不一定是最小值，再模lcm(23,28,29)即可

\#include<iostream>  
\#include<cstdio>  
\#include<algorithm>  
using namespace std;  
int main()  
\{  
int p,e,i,d,N=0;  
int days;  
while(cin>>p>>e>>i>>d)\{  
if(p==-1&&e==-1&&i==-1&&d==-1)  
break;  
days=(p\*5544+e\*14421+i\*1288)%21252;//大中华的剩余定理  
if(days-d<=0)  
   days+=21252;  
cout<<"Case "<<++N<<": the next triple peak occurs in "<<days-d<<" days."<<endl;  
\}

//下面就是把5544,14421,1288三个基础书暴力找出来，然后就可以直接代入公式了  
/\*for(int i=28\*23;;i++)  
    \{  
        if(i%33==1&&i%28==0&&i%23==0)  
        \{  
            printf("%d\\n",i);  
            break;  
        \}  
    \}//1288  
    for(int i=33\*23;;i++)  
    \{  
        if(i%33==0&&i%28==1&&i%23==0)  
        \{  
            printf("%d\\n",i);  
            break;  
        \}  
    \}//14421  
    for(int i=28\*33;;i++)  
    \{  
        if(i%33==0&&i%28==0&&i%23==1)  
        \{  
            printf("%d\\n",i);  
            break;  
        \}  
    \}//5544  
    \*/  
return 0;  
\}