企业官网建设流程全解析

原题来自：POJ 1006

人生来就有三个生理周期，分别为体力、感情和智力周期，它们的周期长度为 23 天、28 天和 33 天。每一个周期中有一天是高峰。在高峰这天，人会在相应的方面表现出色。例如，智力周期的高峰，人会思维敏捷，精力容易高度集中。因为三个周期的周长不同，所以通常三个周期的高峰不会落在同一天。对于每个人，我们想知道何时三个高峰落在同一天。对于每个周期，我们会给出从当前年份的第一天开始，到出现高峰的天数（不一定是第一次高峰出现的时间）。

你的任务是给定一个从当年第一天开始数的天数，输出从给定时间开始（不包括给定时间）下一次三个高峰落在同一天的时间（距给定时间的天数）。

例如：给定时间为 10，下次出现三个高峰同天的时间是 12，则输出 2（注意这里不是 3）。

本题有多组数据。

对于每组数据，输入四个整数 p,e,i 和 d。p,e,i 分别表示体力、情感和智力高峰出现的时间（时间从当年的第一天开始计算）。d 是给定的时间，可能小于 p,e 或 i。

当 p=e=i=d=−1 时，输入数据结束。

从给定时间起，下一次三个高峰同天的时间（距离给定时间的天数）。采用以下格式：

Case 1: the next triple peak occurs in 1234 days.

注意：即使结果是 1 天，也使用复数形式 days。

数据范围与提示：

所有给定时间是非负的并且小于 365，所求的时间小于 21252。

1. 题意转换

剥去“体力、感情、智力”这层生理周期的外衣，这道题本质上是在求解一个一元线性同余方程组： 已知三个固定周期 m1​=23,m2​=28,m3​=33，以及三个余数 a1​=p,a2​=e,a3​=i。我们需要求出一个天数 x，满足：

x≡p(mod23)

x≡e(mod28)

x≡i(mod33)

在求出满足条件的最小非负整数解 x 后，找到严格大于给定天数 d的那个解，并输出它们之间的差值 (x−d)。

2. 思考过程与解题思路

• 第一直觉：暴力跳步法（枚举法）初学者的直觉通常是：从 d+1 天开始，一天一天往后枚举，判断是不是同时满足上面三个取模条件。稍微聪明一点的暴力是：先找到满足第一个条件的某一天，然后每次加上 23 去找满足第二个条件的，接着再每次加上 23×28 去找第三个。为什么暴力能过但不优雅？三个周期的最小公倍数（总周期）是 23×28×33=21252。在最坏情况下，暴力需要循环数万次。虽然 POJ 给的时间限制较宽，暴力不会超时，但如果在高规格比赛中遇到 10^18 级别的模数，暴力肯定不得行。

• 正解推导：同余方程组的合并这题是标准得不能再标准的中国剩余定理（CRT）模型，因为模数全部互质。但我们在实际做题时，通常直接套用更具普适性的扩展中国剩余定理（EXCRT），因为这个既可以解决模数两两互质的情况，也可以解决不互质的情况。 面对这三个方程，我们只需要：

  1. 先算出前两个方程的公共解ans，并求出它们的总周期lcm。

  2. 拿着这个“半成品”去和第三个方程合并，用扩欧求出跨越的步长。

  3. 合并完毕后，我们就能得到这三者在 21252 天内的唯一共同高峰日。

3. 算法设计与样例推演

• 核心算法：利用EXCRT迭代合并同余方程。 每轮合并的核心状态转移方程式为：

  lcm⋅x0​+m[i]⋅y0​=a[i]−ans

  利用扩欧解出 x0​ 后，真实步数为：

  x0​=(x0​×(a[i]−ans)/d​) (mod (m[i]/d)​)

• 极简数据手玩推演（带入样例 2：p=0, e=0, i=0, d=100）： 此时 a={0,0,0,0}，m={0,23,28,33}。

  1. 地基初始化：ans = a[1] = 0，lcm = 23。

  2. 合并第二个方程 (28)： 我们要解 23⋅x0​+28⋅y0​=0−0=0。 显然步长 x0​=0。 更新解：ans = 0 + 0 * 23 = 0，lcm = 23 * 28 = 644。

  3. 合并第三个方程 (33)： 解 644⋅x0​+33⋅y0​=0−0=0。 同样步长 x0​=0。 更新解：ans = 0 + 0 * 644 = 0，lcm = 644 * 33 = 21252。

  4. 尾盘平移处理： 算出的绝对高峰日是第0天。但是题目给定的当前时间是 d=100。 因为要求“下一次”发生的时间，所以我们要加上总周期 21252，直到ans > 100。 平移后ans = 21252。输出答案：21252−100=21152。与样例输出分毫不差。

4. 时空复杂度分析

• 时间复杂度：O(T⋅log(max M))。对于每一组输入，只需进行 2 次exgcd操作合并三个方程。由于底层全是辗转相除法，单次查询时间极短，相当于 O(1)，哪怕有 10^5 组数据也能瞬间解决。

• 空间复杂度：O(1)。只用到了一维长度为 4 的数组存储模数和余数，内存消耗几乎为零。

5. 坑点与易错总结

1. 物理概念的张冠李戴：很多同学读题时，会误把输入的 p,e,i 当作周期去求最小公倍数。记住：23, 28, 33 才是周期（模数），p,e,i 是方程里的余数。

2. 要求的必须是“下一次”：如果直接输出ans - d，当算出的大高峰日比今天早（即ans <= d），就会输出负数。必须通过while(ans <= d) ans += lcm;将天数推移到未来。

3. 负数整除与黄金转正的奇妙碰撞：在代码times = (a[i] - ans) / dd中，由于 23,28,33 两两互质，最大公约数dd永远为 1。虽然a[i] - ans是负数，但负数除以 1 没有任何精度截断误差。随后一句x0 = ((x0 * times) % mod + mod) % mod;完美吸收了所有负数带来的偏移，逻辑自洽，非常漂亮。

4. 多组数据的输出格式：不要漏掉输出格式里的Case X:，且无论天数多少，结尾一律使用复数days.。

6. 完整代码

//这道题是典型的扩展中国剩余定理的应用 #include <iostream> using namespace std; long long p,e,i,d; int idx;//记录当前是第几组测试数组 typedef long long ll; ll m[4]={0,23,28,33};//周期 即模数 ll a[4];//对应每个周期出现高峰的日子 即余数 对应p e i //扩展中国剩余定理 ll exgcd(ll a,ll b,ll &x_,ll &y_){ if(b==0){ x_=1; y_=0; return a; } ll dd=exgcd(b,a%b,x_,y_); ll tmp=x_; x_=y_; y_=tmp-(a/b)*y_; return dd; } //扩展中国剩余定理求解 ll excrt(){ //先把第一个方程的解当作地基 //ans代表当前已经计算出来的答案 ll ans=a[1]; //lcm代表当前所有已合并方程的周期的最小公倍数 //即联合大周期 ll lcm=m[1]; //遍历所有方程 for(int i=2;i<=3;i++){ //先明确当前第i轮的目标方程 //ans+x0*lcm=a[i] （mod m[i]) //转化可以得到方程 //lcm*x0+m[i]*y0=a[i]-ans ll x0,y0; //扩欧求解 ll dd=exgcd(lcm,m[i],x0,y0); //根据裴蜀定理 无解情况 但由题目可以知道 //应该不会出现此情况 if((a[i]-ans)%dd!=0) return -1; //计算缩放倍数 ll times=(a[i]-ans)/dd; //计算新模数 ll mod=m[i]/dd; //计算 x0=((x0*times)%mod+mod)%mod; //计算新的ans 即满足当前所有方程的解 ans=ans+x0*lcm; //计算新lcm 即新的全局周期 lcm=lcm*m[i]/dd; //计算非负最小ans ans=(ans%lcm+lcm)%lcm; } //如果给定的时间在三个高峰同一天之前 if(d<ans) return ans-d; //如果给定时间在三个高峰同一天之后 else{ //从三个高峰同一天不断往后推移一个周期 while(ans<=d) ans=ans+lcm; return ans-d; } } int main(){ ios::sync_with_stdio(false); cin.tie(0); //多组数据输入 while(cin>>p>>e>>i>>d){ if(p==-1&&e==-1&&i==-1&&d==-1) return 0; a[1]=p; a[2]=e; a[3]=i; idx++; cout<<"Case "<<idx<<": the next triple peak occurs in "<<excrt()<<" days.\n"; } return 0; }