【poj1006】 Biorhythms

印度阿三17 2019-09-07

展開全文

點擊題目鏈接

Biorhythms
Time Limit: 1000MS Memory Limit: 10000K

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.

題意理解

??人自出生起就有體力，情感和智力三個生理周期，分別為23，28和33天。一個周期內有一天為峰值，在這一天，人在對應的方面（體力，情感或智力）表現(xiàn)最好。通常這三個周期的峰值不會是同一天?，F(xiàn)在給出三個日期，分別對應于體力，情感，智力出現(xiàn)峰值的日期。然后再給出一個起始日期，要求從這一天開始，算出最少再過多少天后三個峰值同時出現(xiàn)。

解題思路1

??參考中國剩余定理SCL、拓展中國剩余定理SCL

??我們易得： $m_1=23，m_2=28，m_3=33$ m1?=23，m2?=28，m3?=33， $a_1=p，a_2=e，a_3=i$ a1?=p，a2?=e，a3?=i，且 $m_1,m_2,m_3$ m1?,m2?,m3?三個數(shù)互質。
??那么我們就直接用模版接口套公式做就可以。

??但這里要注意兩點：

因為SCL中int CRT(int a[],int m[],int n);最后返回的是(ret M)%M。其中M為 $m_1,m_2,m_3$ m1?,m2?,m3?的乘積，所以當 $a_1=0,a_2=0,a_3=0$ a1?=0,a2?=0,a3?=0 的時候。得到的是(0 M)%M=0，得到的答案再減去輸入的d，明顯不符合要求。這時應該得到的正好是M才合理。
如果只解決上面那一種特殊情況，提交代碼還是會WA。因為通過上面那種特殊情況我們可以反思其他的特殊情況：
//提供一組特殊數(shù)據(jù)
//23 28 33 0 21252
//23 28 33 1 21251
//23 28 33 2 21250
//24 29 34 0 1
//24 29 34 1 21252
//24 29 34 2 21251
//46 56 66 0 21252
//46 56 66 1 21251
//46 56 66 2 21250

??原來我們可以發(fā)現(xiàn)，(ret M)%M代表的其實是一個循環(huán)數(shù)，在0~M-1循環(huán)，如果到M，則自動變?yōu)?。所以如果(ret M)%M-d<=0（不在答案范圍），可以用循環(huán)數(shù)把它變?yōu)樵诜秶鷥鹊臄?shù)。

??參考下面代碼操作：
注：如果對兩個函數(shù)接口不熟悉的可以參考中國剩余定理SCL、拓展中國剩余定理SCL這篇博客。

#include <iostream>
using namespace std;

int extend_gcd( int a, int b, int &x, int &y )//拓展歐幾里得
{
	if( b==0 )
	{
		x = 1;
		y = 0;
		return a;
	}
	else
	{
		int r = extend_gcd(b,a%b,y,x);
		y -= x*(a/b);
		return r;
	}
}

int CRT( int a[], int m[], int n )//中國剩余定理
{
	int M = 1;
	for(int i=0;i<n;  i) M *= m[i];
	int ret = 0;
	for(int i=0;i<n;  i)
	{
		int x,y;
		int tm = M/m[i];
		extend_gcd(tm,m[i],x,y);//調用外部函數(shù)：拓展歐幾里得
		ret = (ret tm*x*a[i])%M;
	}
	return (ret M)%M;
}

int main()
{
    ios::sync_with_stdio(0);
    int a[3],m[3]={23,28,33};
    int d,ans,case_i=1;
    while( cin>>a[0]>>a[1]>>a[2]>>d && a[0]!=-1 )
    {
        ans = CRT(a,m,3)-d;
        if( ans<=0 ) ans = 23*28*33 ans;
        cout << "Case " << case_i   << ": the next triple peak occurs in " << ans << " days." << endl;
    }
}

解題思路2

??上面那個思路是讓計算機幫我們做算術，那如果我們想自己動手算直接得答案呢？

??還是參考中國剩余定理SCL、拓展中國剩余定理SCL這篇中分析的結果：

??中國剩余定理的公式：
??設正整數(shù) $m_1,m_2,...,m_k$ m1?,m2?,...,mk?兩兩互素，則同余方程組
?????????? $\begin{cases} x\equiv a_1(mod\space m_1)\x\equiv a_2(mod\space m_2)\x\equiv a_3(mod\space m_3)\\space\space\space\space .\\space\space\space\space .\\space\space\space\space .\x\equiv a_k(mod\space m_k)\end{cases}$ ????????????????????????x≡a1?(mod?m1?)x≡a2?(mod?m2?)x≡a3?(mod?m3?)????.????.????.x≡ak?(mod?mk?)?

??有整數(shù)解。并且在模 $M=m_1\cdot m_2\cdot...\cdot m_k$ M=m1??m2??...?mk?下的解是唯一的，解為
???? $x\equiv(a_1M_1M_1^{-1} a_2M_2M_2^{-1} ... a_kM_kM_k^{-1})mod\space M$ x≡(a1?M1?M1?1? a2?M2?M2?1? ... ak?Mk?Mk?1?)mod?M
??其中 $M_i=M/m_i$ Mi?=M/mi? ，而 $M_i^{-1}$ Mi?1? 為 $M_i$ Mi? 模 $m_i$ mi? 的逆元。

??其中，據(jù)題意易得a1=p，a2=e，a3=i，且M=23*28*33=21252，M1=M/m1=28*33=924，M2=23*33=759，M3=23*28=644，且m1=23，m2=28，m3=33。

??那么困難就在于手算逆元 $M_i^{-1}$ Mi?1?，為了方便表示，我們把 $M_i^{-1}$ Mi?1?記為 $y_i$ yi?，我們根據(jù)逆元的定義： $M_i*y_i\equiv 1(mod\space m_i)$ Mi??yi?≡1(mod?mi?)求解各個 $y_i$ yi? 即可。

??易得三個聯(lián)立方程：

?????????? $\begin{cases} M_1y_1\equiv 1\space(mod\space m_1)\M_2y_2\equiv 1\space(mod\space m_2)\M_3y_3\equiv 1\space(mod\space m_3)\\end{cases}$ ??????M1?y1?≡1?(mod?m1?)M2?y2?≡1?(mod?m2?)M3?y3?≡1?(mod?m3?)?

??我們拿第一個方程來演示同余方程的解法：

?????????? $M_1y_1\equiv 1\space(mod\space m_1)$ M1?y1?≡1?(mod?m1?)
$\Rightarrow$ ????????? $\space\space924y_1\equiv 1\space(mod\space 23)$ ??924y1?≡1?(mod?23)
$\Rightarrow$ ????? $(40*23 4)y_1\equiv 1\space(mod\space 23)$ (40?23 4)y1?≡1?(mod?23)
$\Rightarrow$ ??????????? $4y_1\equiv 1\space(mod\space 23)$ 4y1?≡1?(mod?23)（利用同余式數(shù)乘原理，兩邊同乘6）
$\Rightarrow$ ??????????? $24y_1\equiv 6\space(mod\space 23)$ 24y1?≡6?(mod?23)
$\Rightarrow$ ??????????? $(23*1 1)y_1\equiv 6\space(mod\space 23)$ (23?1 1)y1?≡6?(mod?23)
$\Rightarrow$ ??????????? $y_1\equiv 6\space(mod\space 23)$ y1?≡6?(mod?23)

??即得到 $M_1^{-1}=y_1=6$ M1?1?=y1?=6

??同理，第二個方程的解法：

?????????? $M_2y_2\equiv 1\space(mod\space m_2)$ M2?y2?≡1?(mod?m2?)
$\Rightarrow$ ????????? $\space\space759y_2\equiv 1\space(mod\space 28)$ ??759y2?≡1?(mod?28)
$\Rightarrow$ ????? $(27*28 3)y_2\equiv 1\space(mod\space 28)$ (27?28 3)y2?≡1?(mod?28)
$\Rightarrow$ ??????????? $3y_2\equiv 1\space(mod\space 28)$ 3y2?≡1?(mod?28)（利用同余式數(shù)乘原理，兩邊同乘9）
$\Rightarrow$ ??????????? $27y_2\equiv 9\space(mod\space 28)$ 27y2?≡9?(mod?28)
$\Rightarrow$ ?????? $(28*1-1)y_2\equiv 9\space(mod\space 28)$ (28?1?1)y2?≡9?(mod?28)
$\Rightarrow$ ??????????? $-y_2\equiv 9\space(mod\space 28)$ ?y2?≡9?(mod?28)
$\Rightarrow$ ???????????? $y_2\equiv -9\space(mod\space 28)$ y2?≡?9?(mod?28)
$\Rightarrow$ ???????????? $y_2\equiv (28*1-9)\space(mod\space 28)$ y2?≡(28?1?9)?(mod?28)
$\Rightarrow$ ???????????? $y_2\equiv 19\space(mod\space 28)$ y2?≡19?(mod?28)

??即得到 $M_2^{-1}=y_2=19$ M2?1?=y2?=19

??同理，解得 $M_3^{-1}=y_3=2$ M3?1?=y3?=2

??又 $x\equiv(a_1M_1M_1^{-1} a_2M_2M_2^{-1} a_3M_3M_3^{-1})mod\space M$ x≡(a1?M1?M1?1? a2?M2?M2?1? a3?M3?M3?1?)mod?M，那么代入各個已知的值便可以得到本題的求解公式：

?? $x\equiv(924*6*p 759*19*a_2 644*2*a_3)mod\space 21252$ x≡(924?6?p 759?19?a2? 644?2?a3?)mod?21252
?即 $x\equiv(5544*p 14421*a_2 1288*a_3)mod\space 21252$ x≡(5544?p 14421?a2? 1288?a3?)mod?21252

??參考下面代碼操作：

#include <iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    int p,e,i,d,ans,case_i=1;
    while( cin>>p>>e>>i>>d && p!=-1 )
    {
        ans = (5544*p 14421*e 1288*i)!252-d;
        if( ans<=0 ) ans = 23*28*33 ans;
        cout << "Case " << case_i   << ": the next triple peak occurs in " << ans << " days." << endl;
    }
}

來源：https://www./content-4-442301.html