1 条题解
-
0
思路与算法
三峰日期t需分别满足t与p模23、与e模28、与i模33同余。三个周期两两互质,总周期L=21252。系数5544、14421、1288分别在自己对应周期下余1、在另两个周期下余0,因此t0=(5544p+14421e+1288*i)%L给出同时高峰的日期剩余类。将t0-d规范化到1至L;余数为0时取L,确保严格晚于给定日期。
正确性说明
三个系数的同余性质直接保证线性组合同时满足全部高峰条件。中国剩余定理给出模L唯一解,因此全部三峰日期相差L。把与d的差规范化到严格正的最小代表,得到下一次日期距离,不会把当天误算为下一次。原题提示写“小于21252”与公开0000样例矛盾;周期定义和该样例共同唯一确定距离范围应为1至21252,本题保留原文并附此范围更正。
复杂度
每组只做常数次乘加与取模,时间O(1),空间O(1),初始化常量与编号O(1),多组总时间与组数线性。p、e、i、d都在0至364,long long足够。Case编号每个输入文件从1开始;结束四个-1不计入编号。
易错点
严格不包括给定当天,0000应输出21252。即使只有1天,也保留英文days。输出格式含Case、冒号、句号与空格。峰值日期可能超过单个周期长度,按同余处理即可。独立答案逐天枚举d+1至d+21252,不复用闭式系数。
参考代码(C++11)
#include <iostream> using namespace std; int main() { long long p, e, i, d; unsigned long long number = 0; while (cin >> p >> e >> i >> d) { if (p == -1 && e == -1 && i == -1 && d == -1) break; long long delta = (5544 * p + 14421 * e + 1288 * i - d) % 21252; if (delta <= 0) delta += 21252; cout << "Case " << ++number << ": the next triple peak occurs in " << delta << " days.\n"; } }
- 1