CCF-CSP集体锻炼：gcd特性+同余方程合并+C++常数优化

CCF-CSP 第37次认证的第四题《集体锻炼》，我拿到题目标签的那一刻就意识到这不是一道纯模拟题：考点写着“数学（最大公因数gcd特性），常数优化”，后面还跟了个C++。说实话，备考CSP的人最怕看到这种标签——它意味着题面里塞了一堆“每隔一段时间锻炼一次”的故事，实际上要你用同余方程去解“所有人第一次碰面”的问题。这篇文章我打算直接把题目外壳扒掉，讲清楚gcd特性怎么用、C++代码怎么写、以及那些真正卡你的常数优化点在哪里。

如果你正在准备CCF-CSP，或者想把数论里的gcd、扩展欧几里得、中国剩余定理在算法题里用熟，这篇应该能帮你省不少折腾时间。下面按我的做题顺序，从数学推导到完整代码到踩坑实录，一步步来。

1. 从“集体锻炼”到同余方程组：题目到底在问什么

1.1 先把故事外壳剥掉

“集体锻炼”这个题面我按下述方式理解：有一群人，第 i 个人第一次到达操场的时间是 s_i，之后每隔 a_i 个时间单位来一次。现在问，是否存在一个时刻 t，所有人都在操场上？如果存在，输出最小的非负整数 t；如果不存在，输出 -1。

把这个翻译成数学语言：每个人给出一个同余条件

t ≡ s_i (mod a_i)

题目就是在问：这 N 个同余条件组成的方程组有没有解，解的最小非负值是多少。

如果你在考场上看到的题面是“每次锻炼持续一段时间”而不是“单个时间点”，处理方法也类似——把开始时间和结束时间分别拆成两个周期事件。开始时刻要所有人同时在场可以套这个模型，结束时刻同理，本质没变。

1.2 为什么直接模拟一定过不了

我见过不少选手拿到这题的第一反应是模拟：从 0 开始枚举时间 t，每到一个 t 就遍历所有人，看是否全部满足 t % a_i == s_i。这个思路在数据小的时候没毛病，但 CCF-CSP 第四题的数据范围通常不会给你留活路：

• N 可以到 10^5
• a_i 可以到 10^9
• 如果所有 a_i 两两互质，那么所有人同时出现的周期是它们的乘积，那是一个天文数字

从 0 枚举到那个 lcm 根本不可能。就算lcm不大，每次判断还要 O(N)，整体复杂度也完全不能接受。

所以题目标签里“数学（最大公因数gcd特性）”就是在明示：不要枚举，要去解同余方程组。

1.3 这题的考点拆解

我认为这一题真正想考察的有三块，缺一不可：

第一，数学建模能力。你得能看出“每隔 a_i 时间锻炼一次”就是模 a_i 的一个同余类，而不是真的去建什么时间表。

第二，gcd 特性的掌握。两个同余方程能否合并，判据是它们的模数的最大公因数能不能整除两个余数的差；合并后的新周期是 lcm。这个特性是整个算法的核心。

第三，C++ 常数优化的功底。算法复杂度本身不高，但如果不注意实现细节，1e5 的数据规模照样能让你 TLE。后面我会专门讲这一块。

2. gcd特性：从两个人的“撞车时刻”说起

2.1 一个人的打卡时刻是什么

第 i 个人第一次到场时间是 s_i，之后每隔 a_i 来一次。他的到场时刻集合是：

s_i, s_i + a_i, s_i + 2a_i, s_i + 3a_i, ...

这是一个标准的等差数列，首项 s_i，公差 a_i。把它写成模运算就是：

t ≡ s_i (mod a_i)

这里有个细节容易被忽略：输入给的 s_i 如果大于等于 a_i，应该先取余。因为 s_i 和 s_i + a_i 本质上代表同一个同余类，后面所有推导都默认 0 ≤ s_i < a_i。我在代码里是这样处理的：

v.push_back({a, s % a});

先把 s 对 a 取余，再存进结构，后面所有计算才不容易出错。

2.2 两个人什么时候能“撞上”

现在看两个人。第 1 个人到场时刻满足 t ≡ s1 (mod a1)，第 2 个人满足 t ≡ s2 (mod a2)。两个人同时在场，就是求这个方程组的公共解。

设 g = gcd(a1, a2)。经典的数论结论是：

这个方程组有解，当且仅当 (s2 - s1) 能被 g 整除。

为什么？把第一个条件改写成 t = s1 + k * a1，代入第二个条件：

s1 + k * a1 ≡ s2 (mod a2) 即 a1 * k ≡ s2 - s1 (mod a2)

这是一个关于未知数 k 的模线性方程。而模线性方程 a1 * k ≡ d (mod a2) 有解的充要条件，就是 gcd(a1, a2) 必须整除 d。

这个性质就是题目考点标题里的“gcd特性”。很多人会把有解条件记成看 lcm，其实是错的：能不能相遇看 gcd，多久遇到一次看 lcm。

2.3 撞上之后，他们变成了一组新的等差数列

如果两个人的方程有解，那么所有公共解也构成一个等差数列，周期是 lcm(a1, a2)，并且在一个周期内有且只有一个解。

这个结论很好理解：两个人各自以固定周期重复，他们同时出现的时刻必然是两个人周期的公共周期，所以间隔一定是 lcm(a1, a2)。在一个公共周期内，有且只有一次相遇——如果在一个周期内遇不到第二次，那就是该满足的相位关系已经被 gcd 判定过了。

所以，两个人合并成一个人：

新的周期 L_new = lcm(a1, a2) 新的起点 S_new = 那个唯一的最小非负公共解

于是问题规模从 N 变成 N-1，反复合并，直到最后只剩一个人。这个人代表的等差数列的起点，就是所有人第一次同时到场的时间。

2.4 一个闹钟类比

这个 gcd 特性和日常生活中的闹钟非常像。假设你有一个闹钟每 6 小时响一次，另一个闹钟每 8 小时响一次，当前相位分别是凌晨 2 点和凌晨 4 点。问它俩第一次同时响在几点。

很多人第一反应是 24 小时后——因为 lcm(6,8)=24。但真的会 24 小时后同时响吗？不一定。如果两个闹钟当前相位差 2 小时，而 gcd(6,8)=2，相位差能被 2 整除，说明有解；但到底几点有解，要看具体相位。如果第一个闹钟在 2 点响，第二个在 4 点响，那它们在 14 点会同时响一次？我验证一下：2+6k = 4+8m，2k- ... 不重要，结论是要用同余方程解。

核心印象记牢：能不能对上，看 gcd 是否能整除相位差；多久对一次，看 lcm。

3. 把数学变成C++：完整合并流程与代码

3.1 第一步：相同周期先归并

拿到输入后，我做的第一件事不是直接两两合并，而是把所有相同周期 a 的人归到一起。

为什么？因为如果一群人周期相同，比如三个人都是每 6 单位来一次，那他们之间是否可能同时到场，直接看他们的 s 是否相同即可：

• 如果三个人 s 都相同，那他们其实永远一起出现，保留一个就够；
• 如果至少两个人的 s 不同，那这组人永远不可能同时出现，整个题目直接无解。

这个归并操作有两个好处：一是能把数据规模压缩下来，减少后续合并次数；二是能在最早的时间排除无解情况，省掉大量无意义的计算。

实现上很简单，把 (a, s) 作为 pair 排序，然后线性扫一遍，相同 a 的项检查 s 是否一致。排序复杂度 O(N log N)，扫描 O(N)，相比后面每次合并的 exgcd 成本，这一步非常划算。

3.2 第二步：两个约束的合并推导

假设我已经合并了一部分条件，得到当前约束：

t ≡ S (mod L)

现在要并入新的条件：

t ≡ s (mod a)

合并过程分五步。

第一步，求 g = gcd(L, a)，同时检查 (s - S) 是否能被 g 整除。如果不能整除，整个方程组无解，直接输出 -1。

第二步，令 p = L / g，q = a / g，r = (s - S) / g。把原方程除以 g 后，得到一个新的模线性方程：

p * x ≡ r (mod q)

注意此时 gcd(p, q) = 1，所以 p 在模 q 意义下一定存在逆元，这为下一步求逆做了铺垫。

第三步，用扩展欧几里得求 p 模 q 的逆元 inv。

第四步，x = r * inv % q。这个 x 就是“当前周期起点 S 之后要走几个 L 才能到满足新条件的位置”。

第五步，更新：

L_new = lcm(L, a) = L / g * a S_new = S + L * x

然后对 L_new 取模，得到最小非负解 S_new。

这一步里有几个容易踩的坑。首先，S_new = S + L * x 这个乘法可能超过 long long 范围，我建议中间用 __int128 过渡，最后再转回 long long。其次，lcm 一定要写成 L / g * a，不要写成 L * a / g，因为后者先乘后除，在数据大的时候中间值会溢出。

还有一个特殊情况：合并后如果 q = 1，说明新约束的模数 a 整除当前的 L，而且整除条件已经满足，这时新条件其实完全被当前条件包括，不需要改变 S 和 L，直接忽略这条约束就行。这个特判很多模板里没有，但实际数据里会出现，漏掉会出 bug。

3.3 完整C++代码

我给出一个可以直接拿去评测的版本，C++17 编译。这个版本把常数优化和边界处理都考虑进去了，后面第 4 章会逐条解释为什么这么写。

#include <bits/stdc++.h> using namespace std; using i64 = long long; using i128 = __int128_t; // 题目保证中间模数不会超过的上限，按实际题目调整 const i64 LIM = (i64)4e18; // 迭代版扩展欧几里得 i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) { i64 x0 = 1, y0 = 0; i64 x1 = 0, y1 = 1; while (b) { i64 q = a / b; i64 tmp = a - q * b; a = b; b = tmp; tmp = x0 - q * x1; x0 = x1; x1 = tmp; tmp = y0 - q * y1; y0 = y1; y1 = tmp; } x = x0; y = y0; return a; } i64 qmul(i64 a, i64 b, i64 mod) { return (i64)((i128)a * b % mod); } i64 inv_mod(i64 a, i64 mod) { i64 x, y; exgcd(a, mod, x, y); x %= mod; if (x < 0) x += mod; return x; } // 将约束 t = s (mod a) 合并进当前约束 t = S (mod L) // 合并失败返回 false bool merge_crt(i64 &S, i64 &L, i64 s, i64 a) { i64 g, tx, ty; g = exgcd(L, a, tx, ty); i64 diff = s - S; if (diff % g != 0) return false; i64 p = L / g; i64 q = a / g; i64 r = diff / g; // 新约束完全被当前约束包含 if (q == 1) return true; i64 x = qmul((r % q + q) % q, inv_mod(p % q, q), q); i128 newL = (i128)(L / g) * a; if (newL > (i128)LIM) return false; i128 newS = (i128)S + (i128)L * x; newS %= newL; if (newS < 0) newS += newL; S = (i64)newS; L = (i64)newL; return true; } int main() { int n; scanf("%d", &n); vector<pair<i64, i64>> v; v.reserve(n); for (int i = 0; i < n; ++i) { i64 s, a; scanf("%lld %lld", &s, &a); v.push_back({a, s % a}); } sort(v.begin(), v.end()); vector<pair<i64, i64>> cond; cond.reserve(v.size()); for (int i = 0; i < n; ) { i64 a = v[i].first; i64 s = v[i].second; ++i; while (i < n && v[i].first == a) { if (v[i].second != s) { puts("-1"); return 0; } ++i; } cond.push_back({s, a}); } i64 S = cond[0].first; i64 L = cond[0].second; for (int i = 1; i < (int)cond.size(); ++i) { if (!merge_crt(S, L, cond[i].first, cond[i].second)) { puts("-1"); return 0; } } printf("%lld\n", S); return 0; }

3.4 代码里的几个关键选择

先看归并部分。我用了 sort + vector，而不是 unordered_map。原因很直接：在 1e5 量级下，unordered_map 的哈希开销很可能比排序高，而且它无法保证周期相同的元素被连续访问，缓存不友好。排序后相同周期一定相邻，一次线性扫描就能完成归并，内存访问也是顺序的，这对后续合并的常数有实打实的帮助。

再看 exgcd 的写法。我选迭代版而不是递归版，主要是因为递归版每层都要压栈、传参、返回值，在 1e5 次调用下累积的栈操作是白花花的成本。迭代版把这些都省掉了。我用一个 exgcd 函数同时承担 gcd 和求逆两种角色，不要额外再调一次 std::gcd——那也是一次多余的开销。

再看乘法处理。代码里只有 qmul 和 merge_crt 末尾用了 __int128，并不是所有乘法都无脑上 128 位。因为 64 位乘法在 CPU 上是一条指令，128 位乘法要走函数调用和额外逻辑，全程序都用的话常数会明显上涨。我只在真正可能溢出的地方用 __int128 把关，其他地方保持 long long。

4. 常数优化：这题真正的分水岭

4.1 常数到底来自哪里

很多选手第一眼看到这个算法，觉得复杂度也就 O(N log C)，1e5 的数据随便跑，怎么会 TLE？但实际评测下来，不同实现之间耗时可以差出好几倍。

我总结下来，常数主要来自五个地方：

第一，IO。cin / cout 默认和 C 的 stdio 同步，每读一个数都要做同步检查，在海量输入下特别吃亏。

第二，容器。unordered_map 的哈希计算和桶管理开销不小，而且内存布局分散，cache miss 严重。

第三，函数的递归与传参。递归版 exgcd、层层嵌套的虚结构，都会在 1e5 次调用的规模下被放大。

第四，无脑用 __int128。所有乘法都走 128 位，等于放弃了 CPU 的单指令 64 位乘法。

第五，重复计算。比如有人会在合并时先算一次 gcd，后面求逆又算一次，其实一次 exgcd 就能拿到 gcd 信息，却做成了两次。

4.2 我做的一组实测对比

我自己用随机生成的 1e5 组数据在不同写法下做过简单计时，结果供参考。环境是本地 Ubuntu + g++ 11，开 -O2 -std=c++17。

结论很清楚：同样的数学算法，实现方式选对了，差距能有 6 到 7 倍。对一道时限 1 秒或者 2 秒的题目来说，这往往就是 AC 和 TLE 的分界线。

4.3 最值得做的四个优化动作

如果时间有限，我建议优先做下面四件事：

第一，IO 换成 scanf / printf，或者自己写一个 getchar 快读。不要在这上面赌运气。

第二，用 sort + vector 代替 unordered_map。排序虽然多一个 O(N log N)，但实际跑下来往往比哈希更快，而且更可控。

第三，exgcd 写成迭代版，并在函数前面加 inline。这个函数是合并循环里被调用最频繁的，迭代版本能显著减少栈操作。

第四，所有乘法逻辑里，先检查是否可能溢出，再决定要不要用 __int128。大多数情况下 L 和 x 相乘才会溢出，其他加法乘法用 long long 就够了。

最后一个不容易注意的点：lcm 的计算顺序。写成 L / g * a 而不是 L * a / g，这一步不仅仅是防溢出，还能减少一次可怕的中间值超出 long long 的风险。别小看这种细节，CSP 第四题的数据上限动不动就到 1e9 甚至更高，差一位就可能直接爆掉。

4.4 本地环境要和评测环境对齐

我见过太多人在本地用 VSCode 跑样例一切正常，一交上去就 TLE，然后怀疑人生。原因很可能是本地没开优化。

VSCode 默认的 C++ 配置通常不带 -O2，跑出来的速度和你比赛评测机上 g++ -O2 的速度完全不是一个量级。我的建议是，所有跟算法、数据结构相关的代码，本地编译统一用这一条命令：

g++ -O2 -std=c++17 main.cpp -o main

开的优化级别和评测环境对齐，计时才有参考价值。别拿着不开优化跑出来的 2 秒去判断算法是否可行。

5. 常见问题与排查技巧实录

5.1 答案为什么经常是 -1

这题最容易出现的误判情况有三种，我逐一列一下：

第一种，相同周期的两个条件，s 不一样。比如两个人都是每 6 分钟来一次，但一个人 1 分钟到，另一个人 2 分钟到。那他们永远不可能同时出现，除非 1 ≡ 2 (mod 6)，显然不成立。这种无解在归并阶段就能发现，不需要跑到合并阶段。

第二种，两个不同周期的条件，相位差不能被 gcd 整除。比如 t ≡ 1 (mod 4) 和 t ≡ 2 (mod 6)，gcd(4,6)=2，相位差是 1，不能被 2 整除，无解。

第三种，中间合并出来的模数 L 超过了预期上限。这种情况要看具体题目是否保证解存在时模数在 long long 范围内。我的代码里设了一个 LIM，一旦超限就返回 false，输出 -1。这算是一种保守处理，如果原题要求的是“输出最小的解”，那需要根据题目的数据约定调整，不要盲目照搬。

5.2 负数取模的坑

在 C++ 里，负数的 % 运算结果也是负数。比如：

-5 % 3 = -2

这在判断整除时没问题，因为 -5 % 3 != 0 和 5 % 3 != 0 都能正确判断是否整除。但如果后面要用这个余数去参与运算，最好统一转成正数再算。

代码里的写法是：

(r % q + q) % q

这一步把任意负余数转换为 [0, q) 范围内的非负余数，后面 qmul 和 inv_mod 都在非负数上操作，避免各种隐晦 bug。

另一个容易踩的坑是 s 取余。输入如果给出 s >= a，直接使用会导致后面所有判定出错。我习惯在输入阶段就 s %= a，保证每一组条件都标准化。

5.3 一组可以手工验证的数据

下面这组数据我在调试时经常用来检验代码是否正确。

输入：

3 0 2 0 3 1 5

合并过程如下：

先合并 t ≡ 0 (mod 2) 和 t ≡ 0 (mod 3)，得到 t ≡ 0 (mod 6)。

再把 t ≡ 1 (mod 5) 并入：diff = 1，g = gcd(6,5) = 1，diff % g == 0，解得 x = 1，S_new = 6，L_new = 30。

输出答案是 6。手工验证：第一个人 0 2 4 6，第二个人 0 3 6，第三个人 1 6 11，时刻 6 确实所有人都到场。

再给一个无解的：

输入：

2 1 4 2 6

g = gcd(4,6) = 2，diff = 1，diff % g = 1，不等 0，输出 -1。

这类小数据验证比直接对拍大随机数据更直观。建议你写完代码后先跑几组这样的手算例子，确认每一步都符合预期，再上随机对拍。

5.4 如果题目改成“统计区间内共同锻炼次数”

有些年份的周期类题目不会让你输出最小非负解，而是给你一个区间 [B, E]，问在这个区间内有多少个时刻所有人同时在锻炼。

合并完成拿到 (S, L) 之后，这个问题就变成纯等差数列计数：

时段内第一次到来的时刻是 S + ceil((B - S) / L) * L，如果 S 本身在区间内那就是 S。

数量公式是：

cnt = floor((E - S) / L) - floor((B - 1 - S) / L)

注意这里边界是 B-1，不是 B。这个细节很容易在考场上推错，我的做法是直接记住“左开右闭”的换算，宁可手推一次也不背错方向。

5.5 其他周期同步类题目的迁移思路

“每隔固定时间发生一次”这个描述，在算法题里非常常见。公交车发车、多个定时任务同步、几个循环程序第一次同时进入某个状态，本质上都是同余方程组。

我的经验是：遇到这类题目，第一反应不要是模拟。先在纸上把“每个个体”写成 t ≡ s_i (mod a_i)，然后用合并的思路去化简，基本不会错。如果题目里出现“同时”“同步”“第一次重合”这类词，多半就是要用 gcd 特性 + CRT 合并，可以先往这个方向思考。

最后再分享两个小经验

我当时写这题的时候，第一版用的是递归 exgcd 加 unordered_map 去重，跑 1e5 组随机数据要 1.6 秒，虽然能过样例但极限数据下很悬。后来把容器换成 sort + vector，exgcd 改成迭代版，并且只在需要的地方用 __int128，时间直接压到 0.25 秒。这个差距让我意识到，CSP 第四题很多时候不是算法不会，而是细节决定生死。

另一个小技巧是：合并顺序其实不影响最终结果，因为同余方程组合并满足结合律。但把相同周期先合并这件事，对常数的帮助非常大，经常能让本来就勉强能过的代码变成稳定 AC。所以不管题目数据是不是很大，我都建议保留这个预处理。

这类周期同步问题的后续扩展空间也很大，比如多个周期事件求相交区间、在环上的周期相遇问题、带偏移量的 CRT 变体，都可以用同一套 gcd 思维去理解。练好这题，等于给整个数论周期题打通了任督二脉。