题目链接

传送门

题目大意

有三个循环周期，周期天数分别为 23, 28, 33 。对于某一年，已知某年这三个周期的某一峰值分别是当年的第 p, e, i 天，问从第 d 天开始到最近一个满足三个周期都达到峰值的日期还有多少天。

算法分析

我们设从这一年的第一天开始，到周期都达到峰值的日期还差x天。据此可列出同余方程组：

\left\{\begin{matrix} x \equiv p (mod \; 23) & \\ x \equiv e (mod \; 28) & \\ x \equiv i (mod \; 33) & \end{matrix}\right.

并使用 中国剩余定理 求出此方程组的最小正整数解。

• 先令三个模数的最小公倍数 lcm=23 \times 28 \times 33 ；

• 以方程 x \equiv p(mod \; 23) 为例，这里的 x 既要满足在模 23 意义下与 p 同余，并且为了使答案同时满足三个方程，还要符合是 28 和 33 的倍数的要求；

• 我们可以令 t \times 28 \times 33 \equiv 1 (mod \; 23) ，即 t 是 28 \times 33 模 23 的逆元；

• 把此同余式的两边同时乘以 p ，得 t \times p \times 28 \times 33 \equiv p (mod \; 23) ；

• 那么该方程的一个解就是 t \times p \times 28 \times 33 。 t 可以手算或用 exgcd 解得；

• 对于其他两个方程也按上述方式处理，得到三个 t 的值分别是 6, 19, 2 ，三个解为 x_1, x_2, x_3 。 这个方程组的最小正整数解就是 (\sum x_i) \; mod \; lcm ；

• 最后，若答案 ans>t ，则直接输出 ans-d ； 否则说明今年的峰值已经过去了，就应输出到下一次峰值的天数 ans-d+lcm 。

代码实现

#include <cstdio>
const int lcm=23*28*33;
int main()
{
//    freopen("hdu1370.in", "r", stdin);
//    freopen("hdu1370.out", "w", stdout);
    int t, p, e, i, d, cnt=0;
    scanf("%d", &t);
    while (~scanf("%d%d%d%d", &p, &e, &i, &d)&&~d)
        printf("Case %d: the next triple peak occurs in %d days.\n", ++cnt, ((p*5544+e*14421+i*1288)%lcm+lcm-d-1)%lcm+1);
    // 5544=6*28*33, 14421=19*23*33, 1288=2*23*28
    return 0;
}