1639：Biorhythms

题目描述

人生来就有三个生理周期，分别为体力、感情和智力周期，它们的周期长度为 $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。

样例

样例输入 #1

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

样例输出 #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.

样例解释 #1

• 第一组：$p=0, e=0, i=0, d=0$，表示在第一天三个高峰都出现，给定时间也是 $0$，要求从给定时间之后下一次三个高峰同天的时间。三个周期的最小公倍数是 $23 \times 28 \times 33 = 21252$（因为 $23,28,33$ 互质），所以下一次是 $21252$ 天后。但 $21252$ 天后，三个高峰再次同天。注意 $0$ 天不算，所以输出 $21252$。
• 其他组类似计算。

数据范围与提示

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

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：本题是中国剩余定理的典型应用。三个周期长度分别为 $23,28,33$，它们两两互质。设从当年第一天开始，第 $t$ 天三个高峰同时出现，则有：

$$\begin{cases} t \equiv p \pmod{23} \\ t \equiv e \pmod{28} \\ t \equiv i \pmod{33} \end{cases}$$

我们需要求 $t$ 的最小正整数解，并且要求 $t > d$，且 $t$ 尽可能小（即下一次三个高峰同天的日期）。注意 $p,e,i$ 可能大于对应的周期长度，但题目说小于 $365$，且周期长度 $23,28,33$ 都小于 $365$，所以 $p,e,i$ 可以认为已经模了对应周期？实际上，$p,e,i$ 表示高峰出现的时间，可能是任意非负整数，但我们可以将其模对应周期，因为高峰是周期性的。但题目没有明确说明，但根据样例，$p,e,i$ 都小于对应周期？第一组 $0,0,0$ 小于 $23,28,33$。但后面有 $283,102,23$ 等，$283$ 大于 $23$，但 $283 \bmod 23 = 7$，所以实际体力高峰出现在周期内的第 $7$ 天。因此，我们需要先将 $p,e,i$ 对对应周期取模。

设 $a_1 = p \bmod 23$，$a_2 = e \bmod 28$，$a_3 = i \bmod 33$（如果 $p,e,i$ 已经是余数，则直接使用）。然后解同余方程组：

$$\begin{cases} t \equiv a_1 \pmod{23} \\ t \equiv a_2 \pmod{28} \\ t \equiv a_3 \pmod{33} \end{cases}$$

由于 $23,28,33$ 两两互质，可以直接用中国剩余定理求解。设 $M = 23 \times 28 \times 33 = 21252$，则解为：

$$t = \left( a_1 M_1 inv_1 + a_2 M_2 inv_2 + a_3 M_3 inv_3 \right) \bmod M$$

其中 $M_1 = 28 \times 33 = 924$，$M_2 = 23 \times 33 = 759$，$M_3 = 23 \times 28 = 644$，$inv_1$ 是 $M_1$ 模 $23$ 的逆元，即 $924 \cdot inv_1 \equiv 1 \pmod{23}$，可以计算 $924 \bmod 23 = 4$，所以求 $4 \cdot inv_1 \equiv 1 \pmod{23}$，得 $inv_1 = 6$（因为 $4 \times 6 = 24 \equiv 1 \pmod{23}$）。类似地，$M_2 \bmod 28 = 759 \bmod 28 = 3$，求 $3 \cdot inv_2 \equiv 1 \pmod{28}$，得 $inv_2 = 19$（$3 \times 19 = 57 \equiv 1 \pmod{28}$）。$M_3 \bmod 33 = 644 \bmod 33 = 20$，求 $20 \cdot inv_3 \equiv 1 \pmod{33}$，得 $inv_3 = 17$（$20 \times 17 = 340 \equiv 1 \pmod{33}$）。

因此，解为：

$$t = (a_1 \cdot 924 \cdot 6 + a_2 \cdot 759 \cdot 19 + a_3 \cdot 644 \cdot 17) \bmod 21252$$

注意 $t$ 可能为 $0$，但 $t=0$ 表示第 $0$ 天（即第一天）三个高峰同天。但我们需要 $t > d$，且是下一次。所以如果 $t \le d$，则加上若干个 $M$ 直到 $t > d$。因为 $M=21252$ 是三个周期的公倍数，所以 $t + kM$ 也是解。因此，最终答案 $ans = t - d$，如果 $t \le d$，则 $ans = t + M - d$（直到 $t > d$）。注意 $t$ 可能等于 $d$，题目要求“不包括给定时间”，所以 $t$ 必须严格大于 $d$。

由于题目保证答案小于 $21252$，所以只需计算 $t$ 后，如果 $t \le d$，则 $t = t + M$，然后输出 $t - d$。

注意多组数据，格式要求：Case i: the next triple peak occurs in X days.，其中 i 从 $1$ 开始递增。

另外，注意 $p=e=i=d=-1$ 时结束。