早上在评测系统里刷到这道题的时候我第一反应是“B - Two chandeliers”这个名字挺唬人点进去一看两盏吊灯每盏按各自的周期循环变色问第 k 次“不和谐”的时刻是什么时候。这种题目看名字像是模拟题但稍微扫一眼数据范围就知道暴力扫时间轴一定 T 到姥姥家。真正把这道题做出来之后我发现它其实是一道很典型的“周期性事件统计”题核心工具就是扩展中国剩余定理EXCRT和二分答案两者配合得严丝合缝。这篇博客我就把整个推导过程、实现细节、以及我实际踩过的坑都写下来希望能给正在刷这类题的同学一点参考。1. 题目拆解两盏吊灯的周期问题到底在算什么1.1 先把题意翻译成数学语言题目里两盏吊灯第一盏有 n 个位置第二盏有 m 个位置每个位置都有一个颜色值。从某个时刻开始第一盏灯每个单位时间会切换到下一个位置第 t 个时刻它显示的颜色就是数组 a 的第t mod n个位置第二盏灯同理显示的是数组 b 的第t mod m个位置。如果某一时刻两盏灯显示的颜色相同那就认为这一秒是“和谐”的否则就是不和谐。现在给一个很大的数 k问第 k 个不和谐的时刻具体是哪个时刻。这句话翻译过来其实就是给了两个周期分别为 n 和 m 的序列我们要找时间轴上的事件分布。如果你手上拿的是两个长度几百万的数组直接 for 循环从 t 0 一直往上递增数到第 k 个不和谐的时刻逻辑上没错但 k 的范围可能到 1e18你数到头发白了都数不完。所以关键是把“周期”利用起来而不是把时间轴一条一条地梭哈。我个人的习惯是先把所有变量统一成“时刻 t 从 0 开始”的模型。很多题目里会用第 1 秒、第 2 秒这种 1 基描述但做数论题的时候 0 基会让取模运算干净很多后面代码里的边界也能少踩很多坑。如果你发现原题是 1 基的可以先在输入的时候把数组下标或者查询逻辑做一次便宜转换后面统一按 0 基处理。1.2 为什么暴力解法必然超时假设 n 和 m 都在 2e5 这个量级k 在 1e18 量级那直接枚举时间轴的做法肯定不行。有些人可能会说那我把 a 和 b 拉成同样长度找到一个公共周期 L lcm(n, m)然后在一个 L 内统计不和谐的次数再用 k 整除一下不就行了这个思路方向是对的但里面藏着一个大坑一个公共周期 L 内到底有多少次不和谐如果你还是用两重循环去暴力统计复杂度 O(L) 的代价在 L 很大的时候照样不可接受。这里 L 可能达到 n * m / gcd(n, m) 的量级在 n、m 都是 2e5 的时候L 能到 4e10直接内存和时间双爆炸。所以我们就需要更聪明的办法不直接枚举每个时刻而是反过来枚举“哪些位置组合会在某一时刻同时出现”这个组合的数量通常远小于 L。于是题目就变成了一个数论问题给定两个下标 i 和 j是否存在某个时刻 t使得第一盏灯正好走到位置 i第二盏灯正好走到位置 j这就是一个同余方程组的问题也就是我们接下来要说的扩展中国剩余定理的用武之地。2. 匹配时刻的同余方程模型这是 EXCRT 的核心切入2.1 位置对齐的本质是解同余方程组先看一个具体问题。如果第一盏灯的长度 n 4第二盏灯的长度 m 6。现在我想知道是否存在某个时刻 t使得第一盏灯正好在第 1 个位置下标 1第二盏灯正好在第 5 个位置下标 5。这个条件写出来就是t ≡ 1 (mod 4) t ≡ 5 (mod 6)如果存在这样的 t那这个时刻就是两个指定位置“对上”的时刻。由于两个数组都是周期性的一旦有一组解 t0那么所有解就是t0 k * lcm(4, 6)也就是说这对位置组合每隔 12 个时刻就会重新对齐一次。这里要特别提醒不要下意识认为“只要 a[i] b[j] 就能在某一个时刻对上”。位置对齐这件事跟颜色是否相同其实没有直接关系。真正决定能否对齐的是两个下标之间的相位关系。比如 n 4m 6i 1j 2你会发现 t 永远不可能既等于 1 mod 4 又等于 2 mod 6因为这两个条件本身就是冲突的。所以对于任何一对位置 (i, j)我们首先要判断同余方程组有没有解有解的话这个解落在哪个时刻然后才谈得上“这个时刻颜色匹不匹配”。2.2 普通 CRT 不够用EXCRT 的合并公式推导很多同学第一反应是中国剩余定理CRT。但 CRT 有一个强前提模数之间两两互质。这里的 n 和 m 显然不一定互质4 和 6 就不互质所以我们必须用扩展中国剩余定理EXCRT它不需要模数互质核心是对两个同余方程进行合并。假设现在有两个方程x ≡ r1 (mod m1) x ≡ r2 (mod m2)把第一个方程写成x r1 m1 * t的形式代入第二个方程得到r1 m1 * t ≡ r2 (mod m2) m1 * t ≡ r2 - r1 (mod m2)接下来这个形式化成线性不定方程m1 * t m2 * y r2 - r1设 d gcd(m1, m2)。如果(r2 - r1) % d ! 0整个方程组必然无解。如果有解先用扩展欧几里得算法求出m1 * t m2 * y d的一组特解然后把右边从 d 放大到(r2 - r1)/d倍就能得到 t 的一个特解 t0。最后把所有解合并成新的同余方程x ≡ r1 m1 * t0 (mod lcm(m1, m2))这样两个方程就变成了一个方程。后面再加进来新的方程就继续用同样的方式合并直到所有方程处理完。这也是“扩展中国剩余定理”最常见的两两合并套路。我觉得用一个生活化的类比比较好理解两盏吊灯像两个不同齿数的齿轮在转你想知道某个齿和某个齿会不会在某一次同时咬合。EXCRT 就是专门计算这两个齿轮咬合周期的工具它不看齿的颜色只看齿的位置是否能被同一个时刻“同时触发”。2.3 一个小优化先用 gcd 快速过滤无解组合实际编码的时候如果我们对每一对颜色相同的位置都去跑一次 EXCRT虽然复杂度也不高但总归有点浪费。有个非常简单的预判条件对于方程x ≡ i (mod n) x ≡ j (mod m)设 g gcd(n, m)方程有解的必要且充分条件是i % g j % g。这个结论来自线性同余方程的基本性质本质上是说两个下标必须落在同一个“模 g 的同余类”里。比如 n 4m 6g 2那么 i 为奇数时 j 也必须是奇数i 为偶数时 j 也必须是偶数否则直接跳过不用再算 EXCRT。别看这个小判断不起眼它能帮我们过滤掉大量无效位置对。特别是当 a 和 b 数组里重复颜色很多的时候先做一次% g的过滤能少掉好几次 exgcd 运算。我在自己实现的时候是先建了一个哈希表记录数组 b 中每种颜色出现的所有位置然后遍历数组 a 的每个位置 i去找 b 中同色的所有位置 j先检查i % g j % g通过了再去求具体的对齐时刻。当然如果同色位置对非常多你还可以选择遍历位置数量少的那一侧这是一个启发式的优化能进一步降低枚举成本。3. 二分答案为什么找“第 k 次不和谐”用二分最稳3.1 匹配事件在一个大周期内只会出现一次我们继续看整个时间轴的结构。所有位置对的对齐时刻如果我们只关心“颜色相同”的匹配事件那么每一对满足条件的 (i, j) 都会产生一个初始时刻 x0并且之后每隔 L lcm(n, m) 重复一次。这里有个很重要的结论在同一个长度 L 的周期里每个匹配事件最多出现一次。因为同一个位置对i mod n 和 j mod m 都确定在同一段周期内只可能有一个对齐时刻不可能出现两次。所以我们可以先把所有“匹配事件”对应的初始时刻 x0 收集到一个数组里比如叫matchPos。因为每个事件在 L 周期内最多出现一次所以matchPos里的元素个数就是每周期匹配事件的总次数。这样一来站在一整条时间轴上匹配事件就变成了若干个以 L 为间隔的等差到达序列。接下来的问题就变成了给定任意时间 T怎么快速统计从 0 到 T 这段时间里总共有多少次匹配事件。3.2 如何快速统计任意时间之前的匹配次数假设我们已经有了matchPos数组里面存了所有匹配事件在第一个周期内的位置并且已经排好序。那么对于任意时刻 T匹配事件的总次数可以这样算先数出 T 里面包含了多少个完整的 L 周期也就是full T / L每个完整周期里有matchPos.size()个匹配事件再处理剩下不到一个周期的部分rem T % L只需要统计matchPos里有多少个值不超过rem这一步用upper_bound二分查找就行。把这段写成代码就是long long countMatch(long long T, long long L, const vectorlong long matchPos) { long long full T / L; long long rem T % L; long long cnt (long long)matchPos.size(); long long res full * cnt; res upper_bound(matchPos.begin(), matchPos.end(), rem) - matchPos.begin(); return res; }注意这里的 T 是“从时刻 0 到时刻 T”的闭区间也就是说时刻 T 本身是包含在统计范围内的。如果题目里第 1 个时刻是从 t 1 开始你需要自己换算一下。我写题的时候很容易在这里搞混所以后来干脆全部统一成 0 基闭区间统计。有了这个函数我们就能很快算出在时刻 T 之前一共出现了多少次不和谐事件。因为从 0 到 T 总共包含T 1个时刻其中countMatch(T)个是匹配时刻剩下的就是bad(T) (T 1) - countMatch(T)这个bad(T)随着 T 增大一定是单调不减的因为新增一个时刻要么它是不和谐事件bad 加一要么它是匹配事件bad 保持不变。有了单调性就可以放心地使用二分答案来找第一个满足bad(T) k的 T 了。3.3 二分上界的处理与边界细节二分的时候左边界自然是 0右边界需要认真处理一下。如果不加思考直接设一个很大的数比如4e18不仅可能溢出还会增加二分次数。更好的做法是用倍增法先找一个可行的上界从 1 开始如果当前右边界还不够就不断翻倍直到bad(r) k。long long l 0, r 1; while (bad(r - 1) k) { r 1; }这里为什么用bad(r - 1)而不是bad(r)因为我们要找的是最小的 T 使得 bad(T) 已经达到 k检查r - 1是为了确定在进入区间[r/2, r]之前r - 1还没达到目标。如果你用bad(r)判断倒也不会错只是会多倍增一次代码里足够小心就行。还有一种更直接的上界估计方法每周期不和谐次数是L - matchPos.size()平均下来大约每隔这么久会出现一次不和谐所以答案大概在k * L / (L - matchPos.size())附近。但这个估计在数据极端时会有偏差比如某些匹配事件集中在周期开头导致前面的不和谐密度和后面不一样所以还是倍增法最省心。我实际测试下来在 k 到 1e18 时倍增加二分总共也就多几十次迭代完全不影响效率。二分内部的countMatch如果 matchPos 数组很大可以提前把数组排序然后每次二分内部再做一次upper_bound整体复杂度大概是 O(log(k) * log(|matchPos|))非常稳定。4. 完整实现从公式到可以跑通的代码4.1 数据结构与重要变量设计在写实现之前我先把整个程序分成了几个清晰的阶段读入 n, m, k 和两个数组 a, b。计算 g gcd(n, m)L n / g * m。建立 b 数组的颜色到下标列表的映射比如unordered_mapint, vectorint posB。遍历 a 的下标 i对每种颜色 c a[i]拿到 posB[c] 里的所有下标 j过滤掉i % g ! j % g的组合。对通过过滤的组合解同余方程求出它们在第一个周期内的对齐时刻 x0放进matchPos。对matchPos排序。二分答案。这里有一个点值得单独说一下L n / g * m这个式子应该先除后乘因为n * m可能爆long long而n / g一定是整数先除能有效降低溢出风险。虽然最后 L 本身也可能非常大但至少我们在计算过程中尽量推迟溢出的发生。4.2 核心函数代码讲解扩展中国剩余定理的合并函数是整道题的地基我先把版本贴出来using ll long long; ll exgcd(ll a, ll b, ll x, ll y) { if (b 0) { x 1; y 0; return a; } ll d exgcd(b, a % b, y, x); y - a / b * x; return d; } // 合并两个方程 x ≡ r1 (mod m1), x ≡ r2 (mod m2) // 如果合法返回 true并且把合并后的方程写入 r, m bool mergeEquation(ll r1, ll m1, ll r2, ll m2, ll r, ll m) { ll x, y; ll d exgcd(m1, m2, x, y); ll diff r2 - r1; if (diff % d ! 0) return false; ll mod m2 / d; ll k (diff / d) % mod; // 这里的 x 是 m1*x m2*y d 的特解放大到 diff/d 倍 x (x % mod mod) % mod; x (__int128)x * k % mod; ll lcm m1 / d * m2; r (r1 (__int128)m1 * x) % lcm; m lcm; return true; }这段代码里有几个容易写错的地方。第一x (x % mod mod) % mod是用来把扩展欧几里得求出的特解调整到最小非负剩余防止后面的乘法得到负数结果。第二x (__int128)x * k % mod这一步必须注意乘法可能超过long long的范围因为 x 和 k 理论上都能到 mod 的量级而 mod 又有可能是 1e18 量级这时候普通乘法直接 UB 给你看。第三最后算 lcm 和 r 的时候m1 * x也可能爆所以要转成__int128再取模。__int128在竞赛环境里基本都能用但如果你在某类不支持它的评测机上做项目就得自己写快速乘不过竞赛场景里我一般就直接用了。有了这个合并函数求解位置对 (i, j) 的对齐时刻就很简单了ll solveAlignment(ll i, ll n, ll j, ll m, ll L) { ll r, M; if (!mergeEquation(i, n, j, m, r, M)) return -1; // 无解 // 这里合并结果 M 应该等于 lcm(n, m)也就是 L return r % L; // 把对齐时刻归一到第一个周期 [0, L) }由于我们只关心每个匹配事件的第一个出现位置所以计算完以后对 L 取模放入 matchPos。4.3 完整主流程代码int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll n, m, k; cin n m k; vectorll a(n), b(m); for (auto v : a) cin v; for (auto v : b) cin v; ll g gcd(n, m); ll L n / g * m; unordered_mapll, vectorll posB; for (ll j 0; j m; j) { posB[b[j]].push_back(j); } vectorll matchPos; for (ll i 0; i n; i) { int c a[i]; auto it posB.find(c); if (it posB.end()) continue; for (ll j : it-second) { if (i % g ! j % g) continue; ll r, M; if (!mergeEquation(i, n, j, m, r, M)) continue; matchPos.push_back(r % L); } } sort(matchPos.begin(), matchPos.end()); auto countMatch [](ll T) - ll { ll full T / L; ll rem T % L; ll cnt (ll)matchPos.size(); ll res full * cnt; res upper_bound(matchPos.begin(), matchPos.end(), rem) - matchPos.begin(); return res; }; auto bad [](ll T) - ll { return (T 1) - countMatch(T); }; ll l 0, r 1; while (bad(r - 1) k) { r 1; } while (l r) { ll mid (l r) 1; if (bad(mid) k) r mid; else l mid 1; } cout l \n; return 0; }这个主流程跑出来的结果我拿随机数据和小规模暴力对拍过逻辑上是自洽的。需要注意的是countMatch里的full * cnt两个量都可能很大已经超过long long的可能性是存在的。如果你担心这个问题可以用__int128来保存计数值最后和 k 比较的时候再取出来。真正写题的时候我一般会根据数据范围决定要不要防护但代码里最好还是加上一层毕竟这种地方一旦爆掉了调试起来非常痛苦。5. 实测中踩过的坑5.1 溢出问题lcm 和乘法爆 long long这个坑我基本上每次做扩展中国剩余定理相关的题都会遇到几乎是必修课。比如 n 1e9m 1e9 且互质L 1e18这时候full * cnt和(T - x0) / L 1这类表达式都很容易在中间步骤溢出。我在第一次写这道题的时候二分内部用的是最朴素的逐项统计方式for (ll x0 : matchPos) { if (T x0) match (T - x0) / L 1; }结果 match 本身是long long当 match 逼近 1e18 的时候再往上加 1没问题但T - x0如果 T 也很大倒是还好。真正危险的是后来我为了追求效率改成了 full * cnt两个数相乘直接爆。解决方案有三个一是全程__int128做中间量二是用long double粗略估计再配合特殊判断三是用快速乘。我建议直接上__int128代码可读性最好性能损失也微乎其微。5.2 索引 0 基与 1 基带来的“对不齐”错误很多周期类题目的描述里喜欢用“第 1 个位置”“第 1 秒”这样的表述稍不注意就会把整个同余方程写歪。我举个例子如果题面说第 1 秒时第一盏灯显示 a[1]那么写成同余关系时你如果直接用t ≡ 1 (mod n)去套很可能就把 a 的第 1 个元素当成了下标 0导致后半段所有对齐时刻全部错位。我个人的处理办法是在读入阶段就把所有数组变成 0 基同时把查询也换算成 0 基时间。比如“第 k 个不和谐的时刻”如果从 1 开始计数而我们代码里 bad(T) 统计的是闭区间 [0, T] 内的不和谐事件数那么答案是bad(T) k最小的 T输出的时候如果需要 1 基就输出T 1。如果你坚持全程 1 基也不是不行但取模运算会多出一堆-1极度容易写错。这个坑我建议所有读者自己动手推一遍拿 n 4, m 6a 和 b 都是小样例手动列一下 0 基和 1 基的差别比看十篇文章都管用。5.3 答案上界估计错误导致二分死循环二分本身不太容易死循环但如果你的右边界从一开始就比真实答案小那二分就会一直卡在右边界上返回错误结果。我最初的版本用了r k * L这种粗暴估计结果有一个数据点 k 很大但 L 也很大的时候k * L直接溢出成负数右边界变成-1二分直接原地去世。后来我改成倍增法之后就再也没出过问题。倍增法的好处是不需要提前估算答案的量级它通过不断翻倍把右边界推到一个足够大的点最多翻 60 次左右就覆盖了整个long long范围。配合左边界 0二分次数稳定在 60 次附近非常放心。5.4 匹配事件重复计数的问题如果你像我最开始那样把所有满足a[i] b[j]的位置对都往里塞不加以过滤或者去重可能会出现同一个初始时刻 x0 被多次收集。举个例子如果数组 a 里有两个位置颜色相同比如 a[1] a[3] c而 b 里也有对应同色位置理论上它们会分别产生两个不同的对齐时刻 x0 和 x0但如果两个位置对最后解出来的 x0 恰好相等呢这种情况可能出现吗仔细想想x0 由i mod n和j mod m唯一确定如果 x0 相等那么 i x0 mod nj x0 mod m也就是说位置对本身是唯一的。所以在真正合法的位置对里x0 不会重复。但如果你在过滤阶段没有做i % g j % g的判断用 EXCRT 解出来可能返回同一个 r 吗其实不会因为如果 (i, j) 不同r 在模 L 下也不同。但为了保险起见我在代码里还是会对 matchPos 做一次 sort unique毕竟不怕一万只怕万一多一行代码的成本可以忽略不计。6. 这套组合还能用在哪些题上6.1 识别“周期匹配 第 k 事件”的题型特征刷题刷多了之后你会发现很多题都有一个共同的骨架两个周期事件可能相同也可能不同然后问第 k 次某种状态发生在什么时候。比如两个交通信号灯以不同周期循环问你第 k 次同时变绿两个机器人以不同步长走路问你第 k 次踩到同一个格子。这类问题一旦出现数据范围又很大基本就能锁定是“Chinese Remainder 二分”的组合。识别这种题型的信号有题目中出现两个不同周期的循环序列查询是第 k 次某种事件而不是请你输出某个周期的状态k 的范围比单独一个序列的长度大很多事件是否发生取决于两个序列某个位置的某种关系。遇到这种题第一步永远是找公共周期 L第二步是把“事件”映射到 L 内的有限个初始时刻第三步是二分答案。三步走完代码基本就成型了。6.2 变体求第 k 次“匹配”而不是“不匹配”我们上面讲的都是求第 k 次不和谐也就是匹配事件的反面。如果题目反过来问第 k 次匹配发生在什么时候思路完全一样只是把判断函数换成countMatch(T) k而已。因为匹配事件和之前一样也是周期性的统计函数不需要变只需要把二分和阈值条件改一下。我在写这道题的时候一开始把 bad 函数封装得比较死后来发现如果换个判断条件又要重新写一个逻辑。所以我在项目里尽量把countMatch独立出来让 bad 只是它的一个薄包装。这样不管题目问的是匹配还是不匹配核心统计逻辑都能复用。6.3 EXCRT 作为通用工具的独立价值最后想单独说一句扩展中国剩余定理本身。它不只是这道题的一个零件在很多同余方程组相关的题目里都是核心工具。比如求某个数满足若干个模数不互质的余数条件或者求某些数列的最早相遇时刻都会用到这套 exgcd 合并方程的方法。我建议读者把mergeEquation这个函数背熟它比普通 CRT 的适用范围广得多而且代码量并没有多多少。以后遇到“模数不互质”的第一反应就应该是 EXCRT而不是转过头去试图把数据拆成互质的情况。我在实际编码中还养成了一个习惯每次写完 EXCRT 类型的代码都会用一个小暴力对拍器验证比如随机生成几个同余方程手动枚举小范围 x 检查合并后的结果是否真的同时满足所有方程。这个习惯帮我抓出了至少三次因为取模边界写错导致的隐蔽 bug。虽然对拍会花几分钟时间但在这种数论代码上几分钟的验证往往能省下后期几小时的调试时间。最后再分享一点个人体会这道题做完之后我对“周期性事件统计”这类题的理解提升了一个层次。很多看似是模拟的题目核心其实都在于你能不能看穿事件的重复结构。两盏吊灯的循环本质上就是两个模数 n 和 m 驱动的状态机整个系统每 lcm(n, m) 个时刻完全复刻一次。你能不能在第一个周期内把事件的位置全部找出来能不能在第二个周期开始之后用数学方式“跳过”中间的重复决定了这道题是 O(n m) 还是 O(k) 的差距。我自己的建议是遇到这种题不要急着写代码先拿笔在草稿纸上列出同余方程组把合并过程和二分边界写清楚再动手。数论题最怕的不是思路难而是细节多一个符号错位就能让你 Debug 到怀疑人生。把 0 基时间、闭区间统计、先除后乘这三个习惯刻进肌肉记忆里这类题你也能稳定拿下。