这道题我打了三遍。CCF-CSP第37次认证的第四题《集体锻炼》我用C交了三版才把分数拿满。第一版TLE第二版WA第三版才真正摸清楚它考的东西最大公因数gcd的特殊性质外加一整套常数优化手段。题目表面看像是模拟“某个时间点谁在锻炼”实际上所有状态都在60这个周期里转而60的因子只有12个——这12个因子就是整道题的题眼。这篇文章的定位很明确给正在准备CCF-CSP、想在第四题上稳定拿分的选手也给那些想练一练数论思维和代码提速的竞赛入门者。我不会贴原题原文而是把它抽象成一个“能跑通”的核心模型围绕这个模型讲解三层优化思路。你先记住一个结论这道题的价值不在于背gcd模板而在于把“巨大时间范围内的判断”压缩到“60以内的预处理查表”。下面按我三次提交的顺序完整复盘。1. 先别急着写模拟读懂题目在考什么1.1 “集体锻炼”为什么不是纯模拟题我的第一反应非常直接维护一个时间戳每个人每隔几分钟锻炼一次查询第t分钟有多少人在锻炼。这就是纯模拟每人一个计数器每次查询扫一遍员工数组判断t % d[i] 0。看起来天经地义没有逻辑错误但提交之后大数据点直接超时。关键在于数据范围。这类题目里的时间戳经常给到10^12甚至更大员工数和查询次数也普遍在10^5、10^6量级。如果每个查询都去遍历所有员工复杂度就是O(n * m)最坏情况轻松冲到10^10次取模运算。取模本身在CPU上就是几十个时钟周期的开销叠加起来完全不可能在时限内跑完。所以当你看到“集体锻炼”这种题目名第一件事绝对不应该是写while (t)而是先想这个时间系统有没有周期性答案是有。我抽象出的核心模型是这样的有n个员工每个员工有一个锻炼间隔dd取60的因子查询时刻t统计所有满足t % d 0的员工数。因为所有d都整除60整个系统状态从第0分钟开始每60分钟就完全复现一次。这不是巧合60恰好是1、2、3、4、5、6的最小公倍数也就是lcm(1..6)60。把60拆开看2^2 * 3 * 5它能被1到6全部整除。所以在判断t % d 0时把t加上60的任意倍数结论完全不变。不管题目给出的t有多大先对60取模这一步就能把无限的时间压缩成60个余数。1.2 整除判断的“公因子视角”到这一步很多人会立刻想到预先把每个锻炼间隔d对应的员工数量存进数组再预处理一下“每小时第r分钟有多少员工在锻炼”查询时直接取r t % 60。我第二版就是这么写的确实能从TLE变AC但我后来复盘时发现这并没有完全理解题目想考的数学内核。题目里还有一层更隐蔽的等价关系判断t % d 0其中d是60的因子。这时真正起决定作用的并不是余数r本身而是t和60的最大公因数g gcd(t, 60)。原因很好验证d整除60同时d整除t那么根据最大公因数的定义d一定整除g。反过来如果d整除g那d显然同时整除t和60。所以逻辑可以再往前推一步我根本不用管t具体是多少只要知道g是多少就能一次性把所有处于活跃状态的间隔d全筛出来。进一步地所有员工是否激活完全由g这一个值决定。60的因子只有12个所以所有可能的系统状态最多只有12种。这比按余数分类又压缩了一个维度余数有60个但很多余数对应的激活集合完全一样。举个例子t7和t13余数不同但gcd(7,60)1、gcd(13,60)1它们的激活状态完全相同。这种按gcd分类的思路才贴合题目真正考察的“最大公因数特性”。t % 60 示例g gcd(t%60, 60)被激活的间隔d集合7, 11, 13, 171{1}2, 14, 22, 262{1, 2}3, 9, 21, 273{1, 3}4, 28, 44, 524{1, 2, 4}6, 18, 42, 546{1, 2, 3, 6}12, 24, 36, 4812{1, 2, 3, 4, 6, 12}这张表不用全部背下来核心是理解“状态等价类”这个概念。你要是在考场上一眼看出周期性再用gcd做分类这道题基本就稳了。2. 数学原理深挖gcd和60的“因子家族”2.1 60的约数只有12个这是全题优化的钥匙很多选手忽视了一个基础事实60的正因子只有12个。整道题可以分成三层来看第一层全部可能的时间点t没有上界。第二层t % 60压缩到60个余数。第三层gcd(t % 60, 60)压缩到12个类别。这三层压缩都是无损的因为“第t分钟哪些员工在锻炼”这个问题的答案在这三层映射下保持完全一致。真正有效的信息量只有12个类别。出题人把周期设为60而不是59或61就是因为60有非常丰富的小因子结构能制造足够的区分度同时又能被整除关系完整刻画。对任意整数xgcd(x, 60)只有12种取值1、2、3、4、5、6、10、12、15、20、30、60。这12个数就是60的约数家族。做预处理的时候我们也只需要在这12个数里循环其他数值连看都不用看。这是常数优化的第一个突破点循环范围从60缩小到12看起来只差5倍但配合查询次数放大之后差距非常明显。2.2 从“枚举每个员工”到“查一次表”的计算量对比用一组具体数字来说明这个差异有多恐怖。假设n10^5个员工m10^5次查询。朴素方案每次查询扫10^5个员工总运算量是10^10次取模。现代评测机每秒大概能跑5×10^8到1×10^9次简单运算按最乐观估计也要10秒以上TLE是必然的。查表方案预处理阶段枚举12×12144次累加或者写宽松一点60×12720次都是可以忽略的量级。查询阶段每次只做一次取模、一次数组访问、一次累加总运算量大约10^5量级。这个量级可以在毫秒级完成几乎不占用时间。到这里为止思路已经通了。但常数优化还可以更狠一点这就是我想要强调的重点全程序运行期根本不需要调用一次gcd函数。因为gcd(t, 60) gcd(t % 60, 60)而t % 60只有60种可能你完全可以把这60个gcd值提前算好存成一张表。更极致一点用C的constexpr在编译期就把这张表生成好运行期连欧几里得的几次除法都省掉纯数组访问。这部分细节在第3节代码里具体体现。很多人会问std::gcd本身是O(log n)的算法但60就那么大一次gcd也就几次求余有必要这么抠吗我的回答是单次确实无所谓但“累计”是常数优化的天敌。如果你不小心把gcd写进了查询循环还配合O(n*m)的暴力枚举那常数直接爆炸。常熟优化讲究的就是把所有可省的开销都在源头堵住不浪费任何一个时钟周期。3. 常数优化实录从TLE到满分的三个版本3.1 版本一朴素模拟TLE第一次提交的代码非常短思路原始且天真#include bits/stdc.h using namespace std; int main() { int n, m; scanf(%d%d, n, m); vectorint d(n); for (int i 0; i n; i) scanf(%d, d[i]); while (m--) { long long t; scanf(%lld, t); int ans 0; for (int i 0; i n; i) { if (t % d[i] 0) ans; } printf(%d\n, ans); } return 0; }提交后对应的大数据点全部超时。为什么因为内层循环的取模次数是n*m当n和m同时达到10^5时10^10次取模已经远超评测时限。考场上看到这种题目第一步必须是“把员工和查询拆开看”而不是一上来就双重循环。哪怕你暂时没发现周期也应该意识到双重循环大概率过不了第四题必须想点别的办法。3.2 版本二按余数查表能过但不够本质第二版我吸取了TLE的教训先把每个间隔d的人数统计好再预处理“每小时第r分钟”的答案#include bits/stdc.h using namespace std; int divCnt[61], rCnt[60]; int main() { int n, m; scanf(%d%d, n, m); for (int i 0; i n; i) { int d; scanf(%d, d); divCnt[d]; } for (int d 1; d 60; d) { if (divCnt[d] 0) continue; for (int r 0; r 60; r) { if (r % d 0) rCnt[r] divCnt[d]; } } while (m--) { long long t; scanf(%lld, t); printf(%d\n, rCnt[t % 60]); } return 0; }这段代码复杂度已经是O(n m)理论上能过。但我第一次写它的时候把内层判断写成了d % r 0方向反了结果WA得很惨。为什么呢因为判断“第r分钟是否被间隔d整除”正确的写法是r % d 0意思是“余数r能被d整除”而不是“d能被余数r整除”。这种细节哪怕错了参考答案也只是小范围偏小肉眼极难发现我最后是靠对拍才找出来的。即使修正之后能AC我心里也清楚它还不是这道题最希望选手写出来的解法。因为这里只用了“60周期”把状态分成了60类但其中大量类别是重复的。如果查询量再放大一个数量级或者题目把周期换成别的数这个方案就缺乏扩展性。真正本质的做法是继续压缩到12个gcd类别。3.3 版本三约数枚举编译期gcd表最终AC最终版本做两件关键优化第一预处理循环从60×60改成12×12只枚举60的约数第二把运行时的gcd全部移到编译期用constexpr生成一张60长度的gcd表。代码如下#include bits/stdc.h using namespace std; constexpr int gcd_cx(int a, int b) { return b 0 ? a : gcd_cx(b, a % b); } constexpr arrayint, 60 buildGcdTable() { arrayint, 60 tab{}; for (int i 0; i 60; i) tab[i] gcd_cx(i, 60); return tab; } constexpr arrayint, 60 gcdTab buildGcdTable(); const int divisors[12] {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}; int divCnt[61], gCnt[61]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; for (int i 0; i n; i) { int d; cin d; divCnt[d]; } for (int d : divisors) { if (divCnt[d] 0) continue; for (int g : divisors) { if (g % d 0) gCnt[g] divCnt[d]; } } while (m--) { long long t; cin t; int g gcdTab[t % 60]; cout gCnt[g] \n; } return 0; }这里解释一下gCnt的预处理逻辑。divCnt[d]存的是“间隔恰为d的员工数量”gCnt[g]最终存的是“如果当前时刻的gcd值为g有多少员工处于锻炼状态”。一个间隔为d的员工会在所有满足“d整除g”的类别g里贡献人数所以内层判断写的是g % d 0千万不能写反。如果写反成d % g 0把不该统计的类别也加进来了结果会全面错乱。用constexpr之后运行期一次gcd都不用算了。t % 60是唯一的取模运算查表得到g再查gCnt得到答案。我在本机随机生成nm10^6的数据测试总耗时大概0.3秒就算评测机波动大1秒内也稳收。另外提醒一句CCF-CSP现在的评测环境支持C17constexpr函数完全没问题。如果遇到比较老的编译器直接用static数组手动初始化效果也是一样的。4. 常见问题与排错技巧实录4.1 查询到底按余数r分类还是按gcd值g分类这是我踩过最深的坑也是评论区问得最多的问题。按余数r分类更直观因为确认60是周期之后时间点直接压到[0,59]预处理60个余数对应的答案即可。但按gcd值g分类更本质因为它把“哪些间隔会被整除”这个信息直接聚合了。两者的差别可以这样看分类方式类别总数每次查询开销数学含义t % 6060O(1)查表只用了周期60没利用整除结构gcd(t, 60)12O(1)查表直接对应“被哪些60因子整除”的集合如果题目只是问“当前时间有多少人在锻炼”两种都能AC。但如果题目进一步问“两个时间点的状态是否完全一致”或者“某一个状态模式出现了多少次”那用gcd分类就明显更直接。我在考场上建议优先想gcd因为这种分类方式对“周期数”的因子结构更敏感。万一原题把60换成了其他数比如77你照样能提取77的因子用同一套方法压缩状态。按余数分类只盯着一个具体数字反而缺少这种泛化能力。4.2 预处理方向写反导致WA怎么自查第二个高发错误就是g % d 0和d % g 0的方向问题。拿一个具体例子说明某员工间隔d4当前时刻t12此时ggcd(12,60)12。因为12能被4整除所以这个员工应该被激活判断条件g % d 0成立。但如果写成d % g 0这里4 % 12不等于0员工就会被漏掉最终答案偏小。这类错误非常阴间因为它不是那种“输出全乱”的错而是只错了一部分数据点答案和正确结果差得很小肉眼完全看不出来。我的排查方式只有一个本地对拍。写一个暴力三重循环的朴素版本随机生成若干组小数据跑完之后直接diff两个程序的输出是否完全一致。这个习惯能帮你省掉大量考场调试时间强烈建议养成。4.3 常数优化清单按优先级排复盘整道题我把考场上的常数优化手段总结成一张清单按投入产出比排序第一去掉所有不必要的取模和gcd调用。查询里t % 60是必要的但gcd一定要用查表替代千万不要在查询循环里写std::gcd(t, 60)。第二用快速IO。C的cin默认与C的stdio同步慢得离谱。要么直接用scanf/printf要么在程序开头写ios::sync_with_stdio(false); cin.tie(nullptr);。第三只读表放全局数组或static。局部大数组在栈上分配某些评测环境下首次访问会慢全局数组的访问速度更稳定。第四预处理循环只遍历有价值的数据。60的因子就12个用const int divisors[12]不要闭着眼睛从1到60全扫。第五能用int绝不用long long。员工数量、答案、预处理表都用int只有原始时间t需要用long long。而且记得先取余再转类型不要为了一个大整数破坏整个流水线的位宽。4.4 这个套路还能迁移到哪些题最后说一点扩展。凡是题目出现“时间t很大、事件间隔是若干固定数”这类描述都可以先思考周期把所有间隔取最小公倍数lcm如果lcm可控在几百以内就把时间空间压缩到lcm大小再进一步取“判断条件涉及的数的全部因子”作为状态类别往往还能再压缩一个维度。我后来做过一些类似的题包括模拟多路公交车到站的、模拟图书馆座位占用的核心都是这个思路。区别只在于lcm具体是多大。如果lcm只有几百直接存几百个状态就行如果lcm大到几万就要考虑用线段树或者其他数据结构去做查询但“先化简、再查表”的思想完全一致。还有一个考场实用技巧如果题目明确所有间隔都来自60的因子你可以在备考阶段直接把12个因子背下来省得临场再去枚举。它们就是1、2、3、4、5、6、10、12、15、20、30、60。这个清单我到现在都还记得做题时直接写进数组就行。老实说我第一次看到这道题时以为是模拟题第二次以为是周期查表直到把gcd分类写进代码才真正觉得这道题“通了”。事后复盘我最受益的不是记住了gcd模板而是一个思维习惯遇到“大时间、小周期”的系统先压缩状态再用状态批量回答查询最后把所有能离线算的都放在预处理阶段。如果你也在准备CCF-CSP第四题不要一上来就追求满分先把暴力分拿满再用查表优化逐步提速。这道《集体锻炼》正好是练“先用数学化简、再做常数优化”的极佳样例。希望这篇复盘能帮你少交两版TLE。如果你用这套模板解了其他题目欢迎一起交流心得。