题目描述人的一生中存在三个周期体力周期232323天、情绪周期282828天和智力周期333333天。每个周期都有一个峰值日。给定从年初开始计算的三个周期的峰值出现日期ppp、eee、iii以及一个当前日期ddd从年初开始计算且ddd可能小于ppp、eee或iii要求计算从ddd到下一个“三重峰值日”即三个峰值同时出现的日期所间隔的天数。若三重峰值日恰好出现在ddd则需计算到下一个三重峰值日的天数。所有输入值非负且不超过365365365保证在给定日期后的212522125221252天内必有一个三重峰值日。输入以-1 -1 -1 -1结束。输入格式输入包含多个测试用例。每个测试用例占一行包含四个整数p,e,i,dp, e, i, dp,e,i,d分别表示体力、情绪、智力周期的峰值日以及当前日期。所有值均为非负且不超过365365365。输入以一行-1 -1 -1 -1结束。输出格式对于每个测试用例输出一行格式为Case k: the next triple peak occurs in x days.其中kkk为测试用例编号从111开始xxx为从ddd到下一个三重峰值日的天数。即使x1x 1x1也使用复数形式days。样例输入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样例输出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.题目分析设三重峰值日为xxx则xxx必须满足以下同余方程组{x≡p(mod23)x≡e(mod28)x≡i(mod33) \begin{cases} x \equiv p \pmod{23}\\ x \equiv e \pmod{28}\\ x \equiv i \pmod{33} \end{cases}⎩⎨⎧​x≡p(mod23)x≡e(mod28)x≡i(mod33)​由于232323、282828、333333两两互质该方程组在模M23×28×3321252M 23 \times 28 \times 33 21252M23×28×3321252的意义下有唯一解。中国剩余定理CRT\texttt{CRT}CRT可直接求出最小非负解x0x_0x0​0≤x0M0 \le x_0 M0≤x0​M。题目要求从ddd之后不含ddd的下一个三重峰值日因此需要找到满足xdx dxd且x≡x0(modM)x \equiv x_0 \pmod{M}x≡x0​(modM)的最小整数。若x0≤dx_0 \le dx0​≤d则需加上若干个MMM使其大于ddd。最终答案为x−dx - dx−d。由于M21252M 21252M21252且题目保证答案在212522125221252天内枚举也能通过但CRT\texttt{CRT}CRT方法更简洁。解题思路使用扩展欧几里得算法实现中国剩余定理。设a[p,e,i]a [p, e, i]a[p,e,i]m[23,28,33]m [23, 28, 33]m[23,28,33]M23×28×3321252M 23 \times 28 \times 33 21252M23×28×3321252。对于每个模数mim_imi​计算MiM/miM_i M / m_iMi​M/mi​然后求MiM_iMi​在模mim_imi​下的逆元xix_ixi​即Mixi≡1(modmi)M_i x_i \equiv 1 \pmod{m_i}Mi​xi​≡1(modmi​)。则x0∑i02aiMixi mod Mx_0 \sum_{i0}^{2} a_i M_i x_i \bmod Mx0​∑i02​ai​Mi​xi​modM。得到x0x_0x0​后若x0≤dx_0 \le dx0​≤d则将其加上⌊(d−x0)/M⌋1\lfloor (d - x_0) / M \rfloor 1⌊(d−x0​)/M⌋1倍的MMM使其成为大于ddd的最小整数。最终输出x−dx - dx−d。代码实现// Biorhythms// UVa ID: 756// Verdict: Accepted// Submission Date: 2018-12-24// UVa Run Time: 0.000s//// 版权所有C2018邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;voidextgcd(inta,intb,intx,inty){if(b0)x1,y0;else{extgcd(b,a%b,x,y);inttx-a/b*y;xy,yt;}}intCRT(inta[],intm[],intn,intd){intM1,r0;for(inti0;in;i)M*m[i];for(inti0,Mi,x,y;in;i){MiM/m[i];extgcd(Mi,m[i],x,y);r(ra[i]*Mi*x)%M;}if(rd)r((d-r)/M1)*M;returnr;}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intp,e,i,d,cases0;while(cinpeid){if(p-1)break;inta[]{p,e,i};intm[]{23,28,33};intrCRT(a,m,3,d);coutCase cases: the next triple peak occurs in ;cout(r-d) days.\n;}return0;}总结本题是典型的中国剩余定理应用。三个模数两两互质使得CRT\texttt{CRT}CRT可以直接给出唯一解。注意处理x0≤dx_0 \le dx0​≤d的情况需增加MMM的整数倍以得到下一个峰值。由于MMM不大也可用枚举法但CRT\texttt{CRT}CRT方法更加通用且高效时间复杂度O(log⁡min⁡(mi))O(\log \min(m_i))O(logmin(mi​))空间O(1)O(1)O(1)。实现时注意扩展欧几里得求逆元以及取模运算保证结果非负。该解法清晰简洁适用于任意数量的两两互质模数的同余方程组。