【题目描述】原题来自POJ 1006人生来就有三个生理周期分别为体力、感情和智力周期它们的周期长度为 23 天、28 天和 33 天。每一个周期中有一天是高峰。在高峰这天人会在相应的方面表现出色。例如智力周期的高峰人会思维敏捷精力容易高度集中。因为三个周期的周长不同所以通常三个周期的高峰不会落在同一天。对于每个人我们想知道何时三个高峰落在同一天。对于每个周期我们会给出从当前年份的第一天开始到出现高峰的天数不一定是第一次高峰出现的时间。你的任务是给定一个从当年第一天开始数的天数输出从给定时间开始不包括给定时间下一次三个高峰落在同一天的时间距给定时间的天数。例如给定时间为 10下次出现三个高峰同天的时间是 12则输出 2注意这里不是 3。【输入】本题有多组数据。对于每组数据输入四个整数 p,e,i 和 d。p,e,i 分别表示体力、情感和智力高峰出现的时间时间从当年的第一天开始计算。d 是给定的时间可能小于 p,e 或 i。当 peid−1 时输入数据结束。【输出】从给定时间起下一次三个高峰同天的时间距离给定时间的天数。采用以下格式Case 1: the next triple peak occurs in 1234 days.注意即使结果是 1 天也使用复数形式 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.【提示】数据范围与提示所有给定时间是非负的并且小于 365所求的时间小于 21252。1. 题意转换剥去“体力、感情、智力”这层生理周期的外衣这道题本质上是在求解一个一元线性同余方程组 已知三个固定周期 m123,m228,m333以及三个余数 a1p,a2e,a3i。我们需要求出一个天数 x满足x≡p(mod23)x≡e(mod28)x≡i(mod33)在求出满足条件的最小非负整数解 x 后找到严格大于给定天数 d的那个解并输出它们之间的差值 (x−d)。2. 思考过程与解题思路第一直觉暴力跳步法枚举法初学者的直觉通常是从 d1 天开始一天一天往后枚举判断是不是同时满足上面三个取模条件。稍微聪明一点的暴力是先找到满足第一个条件的某一天然后每次加上 23 去找满足第二个条件的接着再每次加上 23×28 去找第三个。为什么暴力能过但不优雅三个周期的最小公倍数总周期是 23×28×3321252。在最坏情况下暴力需要循环数万次。虽然 POJ 给的时间限制较宽暴力不会超时但如果在高规格比赛中遇到 10^18 级别的模数暴力肯定不得行。正解推导同余方程组的合并这题是标准得不能再标准的中国剩余定理CRT模型因为模数全部互质。但我们在实际做题时通常直接套用更具普适性的扩展中国剩余定理EXCRT因为这个既可以解决模数两两互质的情况也可以解决不互质的情况。 面对这三个方程我们只需要先算出前两个方程的公共解ans并求出它们的总周期lcm。拿着这个“半成品”去和第三个方程合并用扩欧求出跨越的步长。合并完毕后我们就能得到这三者在 21252 天内的唯一共同高峰日。3. 算法设计与样例推演核心算法利用EXCRT迭代合并同余方程。 每轮合并的核心状态转移方程式为lcm⋅x0m[i]⋅y0a[i]−ans利用扩欧解出 x0 后真实步数为x0(x0×(a[i]−ans)/d) (mod (m[i]/d))极简数据手玩推演带入样例 2p0, e0, i0, d100 此时 a{0,0,0,0}m{0,23,28,33}。地基初始化ans a[1] 0lcm 23。合并第二个方程 (28) 我们要解 23⋅x028⋅y00−00。 显然步长 x00。 更新解ans 0 0 * 23 0lcm 23 * 28 644。合并第三个方程 (33) 解 644⋅x033⋅y00−00。 同样步长 x00。 更新解ans 0 0 * 644 0lcm 644 * 33 21252。尾盘平移处理 算出的绝对高峰日是第0天。但是题目给定的当前时间是 d100。 因为要求“下一次”发生的时间所以我们要加上总周期 21252直到ans 100。 平移后ans 21252。输出答案21252−10021152。与样例输出分毫不差。4. 时空复杂度分析时间复杂度O(T⋅log(max M))。对于每一组输入只需进行 2 次exgcd操作合并三个方程。由于底层全是辗转相除法单次查询时间极短相当于 O(1)哪怕有 10^5 组数据也能瞬间解决。空间复杂度O(1)。只用到了一维长度为 4 的数组存储模数和余数内存消耗几乎为零。5. 坑点与易错总结物理概念的张冠李戴很多同学读题时会误把输入的 p,e,i 当作周期去求最小公倍数。记住23, 28, 33 才是周期模数p,e,i 是方程里的余数。要求的必须是“下一次”如果直接输出ans - d当算出的大高峰日比今天早即ans d就会输出负数。必须通过while(ans d) ans lcm;将天数推移到未来。负数整除与黄金转正的奇妙碰撞在代码times (a[i] - ans) / dd中由于 23,28,33 两两互质最大公约数dd永远为 1。虽然a[i] - ans是负数但负数除以 1 没有任何精度截断误差。随后一句x0 ((x0 * times) % mod mod) % mod;完美吸收了所有负数带来的偏移逻辑自洽非常漂亮。多组数据的输出格式不要漏掉输出格式里的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(b0){ x_1; y_0; return a; } ll ddexgcd(b,a%b,x_,y_); ll tmpx_; x_y_; y_tmp-(a/b)*y_; return dd; } //扩展中国剩余定理求解 ll excrt(){ //先把第一个方程的解当作地基 //ans代表当前已经计算出来的答案 ll ansa[1]; //lcm代表当前所有已合并方程的周期的最小公倍数 //即联合大周期 ll lcmm[1]; //遍历所有方程 for(int i2;i3;i){ //先明确当前第i轮的目标方程 //ansx0*lcma[i] mod m[i]) //转化可以得到方程 //lcm*x0m[i]*y0a[i]-ans ll x0,y0; //扩欧求解 ll ddexgcd(lcm,m[i],x0,y0); //根据裴蜀定理 无解情况 但由题目可以知道 //应该不会出现此情况 if((a[i]-ans)%dd!0) return -1; //计算缩放倍数 ll times(a[i]-ans)/dd; //计算新模数 ll modm[i]/dd; //计算 x0((x0*times)%modmod)%mod; //计算新的ans 即满足当前所有方程的解 ansansx0*lcm; //计算新lcm 即新的全局周期 lcmlcm*m[i]/dd; //计算非负最小ans ans(ans%lcmlcm)%lcm; } //如果给定的时间在三个高峰同一天之前 if(dans) return ans-d; //如果给定时间在三个高峰同一天之后 else{ //从三个高峰同一天不断往后推移一个周期 while(ansd) ansanslcm; return ans-d; } } int main(){ ios::sync_with_stdio(false); cin.tie(0); //多组数据输入 while(cinpeid){ if(p-1e-1i-1d-1) return 0; a[1]p; a[2]e; a[3]i; idx; coutCase idx: the next triple peak occurs in excrt() days.\n; } return 0; } 
长河君 · 2026/10/6 2:47:47 · 阅读 1.2k Biorhythms（信息学奥赛一本通- P1639）
【题目描述】原题来自POJ 1006人生来就有三个生理周期分别为体力、感情和智力周期它们的周期长度为 23 天、28 天和 33 天。每一个周期中有一天是高峰。在高峰这天人会在相应的方面表现出色。例如智力周期的高峰人会思维敏捷精力容易高度集中。因为三个周期的周长不同所以通常三个周期的高峰不会落在同一天。对于每个人我们想知道何时三个高峰落在同一天。对于每个周期我们会给出从当前年份的第一天开始到出现高峰的天数不一定是第一次高峰出现的时间。你的任务是给定一个从当年第一天开始数的天数输出从给定时间开始不包括给定时间下一次三个高峰落在同一天的时间距给定时间的天数。例如给定时间为 10下次出现三个高峰同天的时间是 12则输出 2注意这里不是 3。【输入】本题有多组数据。对于每组数据输入四个整数 p,e,i 和 d。p,e,i 分别表示体力、情感和智力高峰出现的时间时间从当年的第一天开始计算。d 是给定的时间可能小于 p,e 或 i。当 peid−1 时输入数据结束。【输出】从给定时间起下一次三个高峰同天的时间距离给定时间的天数。采用以下格式Case 1: the next triple peak occurs in 1234 days.注意即使结果是 1 天也使用复数形式 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.【提示】数据范围与提示所有给定时间是非负的并且小于 365所求的时间小于 21252。1. 题意转换剥去“体力、感情、智力”这层生理周期的外衣这道题本质上是在求解一个一元线性同余方程组 已知三个固定周期 m123,m228,m333以及三个余数 a1p,a2e,a3i。我们需要求出一个天数 x满足x≡p(mod23)x≡e(mod28)x≡i(mod33)在求出满足条件的最小非负整数解 x 后找到严格大于给定天数 d的那个解并输出它们之间的差值 (x−d)。2. 思考过程与解题思路第一直觉暴力跳步法枚举法初学者的直觉通常是从 d1 天开始一天一天往后枚举判断是不是同时满足上面三个取模条件。稍微聪明一点的暴力是先找到满足第一个条件的某一天然后每次加上 23 去找满足第二个条件的接着再每次加上 23×28 去找第三个。为什么暴力能过但不优雅三个周期的最小公倍数总周期是 23×28×3321252。在最坏情况下暴力需要循环数万次。虽然 POJ 给的时间限制较宽暴力不会超时但如果在高规格比赛中遇到 10^18 级别的模数暴力肯定不得行。正解推导同余方程组的合并这题是标准得不能再标准的中国剩余定理CRT模型因为模数全部互质。但我们在实际做题时通常直接套用更具普适性的扩展中国剩余定理EXCRT因为这个既可以解决模数两两互质的情况也可以解决不互质的情况。 面对这三个方程我们只需要先算出前两个方程的公共解ans并求出它们的总周期lcm。拿着这个“半成品”去和第三个方程合并用扩欧求出跨越的步长。合并完毕后我们就能得到这三者在 21252 天内的唯一共同高峰日。3. 算法设计与样例推演核心算法利用EXCRT迭代合并同余方程。 每轮合并的核心状态转移方程式为lcm⋅x0m[i]⋅y0a[i]−ans利用扩欧解出 x0 后真实步数为x0(x0×(a[i]−ans)/d) (mod (m[i]/d))极简数据手玩推演带入样例 2p0, e0, i0, d100 此时 a{0,0,0,0}m{0,23,28,33}。地基初始化ans a[1] 0lcm 23。合并第二个方程 (28) 我们要解 23⋅x028⋅y00−00。 显然步长 x00。 更新解ans 0 0 * 23 0lcm 23 * 28 644。合并第三个方程 (33) 解 644⋅x033⋅y00−00。 同样步长 x00。 更新解ans 0 0 * 644 0lcm 644 * 33 21252。尾盘平移处理 算出的绝对高峰日是第0天。但是题目给定的当前时间是 d100。 因为要求“下一次”发生的时间所以我们要加上总周期 21252直到ans 100。 平移后ans 21252。输出答案21252−10021152。与样例输出分毫不差。4. 时空复杂度分析时间复杂度O(T⋅log(max M))。对于每一组输入只需进行 2 次exgcd操作合并三个方程。由于底层全是辗转相除法单次查询时间极短相当于 O(1)哪怕有 10^5 组数据也能瞬间解决。空间复杂度O(1)。只用到了一维长度为 4 的数组存储模数和余数内存消耗几乎为零。5. 坑点与易错总结物理概念的张冠李戴很多同学读题时会误把输入的 p,e,i 当作周期去求最小公倍数。记住23, 28, 33 才是周期模数p,e,i 是方程里的余数。要求的必须是“下一次”如果直接输出ans - d当算出的大高峰日比今天早即ans d就会输出负数。必须通过while(ans d) ans lcm;将天数推移到未来。负数整除与黄金转正的奇妙碰撞在代码times (a[i] - ans) / dd中由于 23,28,33 两两互质最大公约数dd永远为 1。虽然a[i] - ans是负数但负数除以 1 没有任何精度截断误差。随后一句x0 ((x0 * times) % mod mod) % mod;完美吸收了所有负数带来的偏移逻辑自洽非常漂亮。多组数据的输出格式不要漏掉输出格式里的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(b0){ x_1; y_0; return a; } ll ddexgcd(b,a%b,x_,y_); ll tmpx_; x_y_; y_tmp-(a/b)*y_; return dd; } //扩展中国剩余定理求解 ll excrt(){ //先把第一个方程的解当作地基 //ans代表当前已经计算出来的答案 ll ansa[1]; //lcm代表当前所有已合并方程的周期的最小公倍数 //即联合大周期 ll lcmm[1]; //遍历所有方程 for(int i2;i3;i){ //先明确当前第i轮的目标方程 //ansx0*lcma[i] mod m[i]) //转化可以得到方程 //lcm*x0m[i]*y0a[i]-ans ll x0,y0; //扩欧求解 ll ddexgcd(lcm,m[i],x0,y0); //根据裴蜀定理 无解情况 但由题目可以知道 //应该不会出现此情况 if((a[i]-ans)%dd!0) return -1; //计算缩放倍数 ll times(a[i]-ans)/dd; //计算新模数 ll modm[i]/dd; //计算 x0((x0*times)%modmod)%mod; //计算新的ans 即满足当前所有方程的解 ansansx0*lcm; //计算新lcm 即新的全局周期 lcmlcm*m[i]/dd; //计算非负最小ans ans(ans%lcmlcm)%lcm; } //如果给定的时间在三个高峰同一天之前 if(dans) return ans-d; //如果给定时间在三个高峰同一天之后 else{ //从三个高峰同一天不断往后推移一个周期 while(ansd) ansanslcm; return ans-d; } } int main(){ ios::sync_with_stdio(false); cin.tie(0); //多组数据输入 while(cinpeid){ if(p-1e-1i-1d-1) return 0; a[1]p; a[2]e; a[3]i; idx; coutCase idx: the next triple peak occurs in excrt() days.\n; } return 0; }