早上在評測系統(tǒng)里刷到這道題的時候我第一反應(yīng)是“B - Two chandeliers”這個名字挺唬人點進去一看兩盞吊燈每盞按各自的周期循環(huán)變色問第 k 次“不和諧”的時刻是什么時候。這種題目看名字像是模擬題但稍微掃一眼數(shù)據(jù)范圍就知道暴力掃時間軸一定 T 到姥姥家。真正把這道題做出來之后我發(fā)現(xiàn)它其實是一道很典型的“周期性事件統(tǒng)計”題核心工具就是擴展中國剩余定理EXCRT和二分答案兩者配合得嚴絲合縫。這篇博客我就把整個推導(dǎo)過程、實現(xiàn)細節(jié)、以及我實際踩過的坑都寫下來希望能給正在刷這類題的同學(xué)一點參考。1. 題目拆解兩盞吊燈的周期問題到底在算什么1.1 先把題意翻譯成數(shù)學(xué)語言題目里兩盞吊燈第一盞有 n 個位置第二盞有 m 個位置每個位置都有一個顏色值。從某個時刻開始第一盞燈每個單位時間會切換到下一個位置第 t 個時刻它顯示的顏色就是數(shù)組 a 的第t mod n個位置第二盞燈同理顯示的是數(shù)組 b 的第t mod m個位置。如果某一時刻兩盞燈顯示的顏色相同那就認為這一秒是“和諧”的否則就是不和諧?，F(xiàn)在給一個很大的數(shù) k問第 k 個不和諧的時刻具體是哪個時刻。這句話翻譯過來其實就是給了兩個周期分別為 n 和 m 的序列我們要找時間軸上的事件分布。如果你手上拿的是兩個長度幾百萬的數(shù)組直接 for 循環(huán)從 t 0 一直往上遞增數(shù)到第 k 個不和諧的時刻邏輯上沒錯但 k 的范圍可能到 1e18你數(shù)到頭發(fā)白了都數(shù)不完。所以關(guān)鍵是把“周期”利用起來而不是把時間軸一條一條地梭哈。我個人的習(xí)慣是先把所有變量統(tǒng)一成“時刻 t 從 0 開始”的模型。很多題目里會用第 1 秒、第 2 秒這種 1 基描述但做數(shù)論題的時候 0 基會讓取模運算干凈很多后面代碼里的邊界也能少踩很多坑。如果你發(fā)現(xiàn)原題是 1 基的可以先在輸入的時候把數(shù)組下標或者查詢邏輯做一次便宜轉(zhuǎn)換后面統(tǒng)一按 0 基處理。1.2 為什么暴力解法必然超時假設(shè) n 和 m 都在 2e5 這個量級k 在 1e18 量級那直接枚舉時間軸的做法肯定不行。有些人可能會說那我把 a 和 b 拉成同樣長度找到一個公共周期 L lcm(n, m)然后在一個 L 內(nèi)統(tǒng)計不和諧的次數(shù)再用 k 整除一下不就行了這個思路方向是對的但里面藏著一個大坑一個公共周期 L 內(nèi)到底有多少次不和諧如果你還是用兩重循環(huán)去暴力統(tǒng)計復(fù)雜度 O(L) 的代價在 L 很大的時候照樣不可接受。這里 L 可能達到 n * m / gcd(n, m) 的量級在 n、m 都是 2e5 的時候L 能到 4e10直接內(nèi)存和時間雙爆炸。所以我們就需要更聰明的辦法不直接枚舉每個時刻而是反過來枚舉“哪些位置組合會在某一時刻同時出現(xiàn)”這個組合的數(shù)量通常遠小于 L。于是題目就變成了一個數(shù)論問題給定兩個下標 i 和 j是否存在某個時刻 t使得第一盞燈正好走到位置 i第二盞燈正好走到位置 j這就是一個同余方程組的問題也就是我們接下來要說的擴展中國剩余定理的用武之地。2. 匹配時刻的同余方程模型這是 EXCRT 的核心切入2.1 位置對齊的本質(zhì)是解同余方程組先看一個具體問題。如果第一盞燈的長度 n 4第二盞燈的長度 m 6?，F(xiàn)在我想知道是否存在某個時刻 t使得第一盞燈正好在第 1 個位置下標 1第二盞燈正好在第 5 個位置下標 5。這個條件寫出來就是t ≡ 1 (mod 4) t ≡ 5 (mod 6)如果存在這樣的 t那這個時刻就是兩個指定位置“對上”的時刻。由于兩個數(shù)組都是周期性的一旦有一組解 t0那么所有解就是t0 k * lcm(4, 6)也就是說這對位置組合每隔 12 個時刻就會重新對齊一次。這里要特別提醒不要下意識認為“只要 a[i] b[j] 就能在某一個時刻對上”。位置對齊這件事跟顏色是否相同其實沒有直接關(guān)系。真正決定能否對齊的是兩個下標之間的相位關(guān)系。比如 n 4m 6i 1j 2你會發(fā)現(xiàn) t 永遠不可能既等于 1 mod 4 又等于 2 mod 6因為這兩個條件本身就是沖突的。所以對于任何一對位置 (i, j)我們首先要判斷同余方程組有沒有解有解的話這個解落在哪個時刻然后才談得上“這個時刻顏色匹不匹配”。2.2 普通 CRT 不夠用EXCRT 的合并公式推導(dǎo)很多同學(xué)第一反應(yīng)是中國剩余定理CRT。但 CRT 有一個強前提模數(shù)之間兩兩互質(zhì)。這里的 n 和 m 顯然不一定互質(zhì)4 和 6 就不互質(zhì)所以我們必須用擴展中國剩余定理EXCRT它不需要模數(shù)互質(zhì)核心是對兩個同余方程進行合并。假設(shè)現(xiàn)在有兩個方程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設(shè) 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))這樣兩個方程就變成了一個方程。后面再加進來新的方程就繼續(xù)用同樣的方式合并直到所有方程處理完。這也是“擴展中國剩余定理”最常見的兩兩合并套路。我覺得用一個生活化的類比比較好理解兩盞吊燈像兩個不同齒數(shù)的齒輪在轉(zhuǎn)你想知道某個齒和某個齒會不會在某一次同時咬合。EXCRT 就是專門計算這兩個齒輪咬合周期的工具它不看齒的顏色只看齒的位置是否能被同一個時刻“同時觸發(fā)”。2.3 一個小優(yōu)化先用 gcd 快速過濾無解組合實際編碼的時候如果我們對每一對顏色相同的位置都去跑一次 EXCRT雖然復(fù)雜度也不高但總歸有點浪費。有個非常簡單的預(yù)判條件對于方程x ≡ i (mod n) x ≡ j (mod m)設(shè) g gcd(n, m)方程有解的必要且充分條件是i % g j % g。這個結(jié)論來自線性同余方程的基本性質(zhì)本質(zhì)上是說兩個下標必須落在同一個“模 g 的同余類”里。比如 n 4m 6g 2那么 i 為奇數(shù)時 j 也必須是奇數(shù)i 為偶數(shù)時 j 也必須是偶數(shù)否則直接跳過不用再算 EXCRT。別看這個小判斷不起眼它能幫我們過濾掉大量無效位置對。特別是當(dāng) a 和 b 數(shù)組里重復(fù)顏色很多的時候先做一次% g的過濾能少掉好幾次 exgcd 運算。我在自己實現(xiàn)的時候是先建了一個哈希表記錄數(shù)組 b 中每種顏色出現(xiàn)的所有位置然后遍歷數(shù)組 a 的每個位置 i去找 b 中同色的所有位置 j先檢查i % g j % g通過了再去求具體的對齊時刻。當(dāng)然如果同色位置對非常多你還可以選擇遍歷位置數(shù)量少的那一側(cè)這是一個啟發(fā)式的優(yōu)化能進一步降低枚舉成本。3. 二分答案為什么找“第 k 次不和諧”用二分最穩(wěn)3.1 匹配事件在一個大周期內(nèi)只會出現(xiàn)一次我們繼續(xù)看整個時間軸的結(jié)構(gòu)。所有位置對的對齊時刻如果我們只關(guān)心“顏色相同”的匹配事件那么每一對滿足條件的 (i, j) 都會產(chǎn)生一個初始時刻 x0并且之后每隔 L lcm(n, m) 重復(fù)一次。這里有個很重要的結(jié)論在同一個長度 L 的周期里每個匹配事件最多出現(xiàn)一次。因為同一個位置對i mod n 和 j mod m 都確定在同一段周期內(nèi)只可能有一個對齊時刻不可能出現(xiàn)兩次。所以我們可以先把所有“匹配事件”對應(yīng)的初始時刻 x0 收集到一個數(shù)組里比如叫matchPos。因為每個事件在 L 周期內(nèi)最多出現(xiàn)一次所以matchPos里的元素個數(shù)就是每周期匹配事件的總次數(shù)。這樣一來站在一整條時間軸上匹配事件就變成了若干個以 L 為間隔的等差到達序列。接下來的問題就變成了給定任意時間 T怎么快速統(tǒng)計從 0 到 T 這段時間里總共有多少次匹配事件。3.2 如何快速統(tǒng)計任意時間之前的匹配次數(shù)假設(shè)我們已經(jīng)有了matchPos數(shù)組里面存了所有匹配事件在第一個周期內(nèi)的位置并且已經(jīng)排好序。那么對于任意時刻 T匹配事件的總次數(shù)可以這樣算先數(shù)出 T 里面包含了多少個完整的 L 周期也就是full T / L每個完整周期里有matchPos.size()個匹配事件再處理剩下不到一個周期的部分rem T % L只需要統(tǒng)計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”的閉區(qū)間也就是說時刻 T 本身是包含在統(tǒng)計范圍內(nèi)的。如果題目里第 1 個時刻是從 t 1 開始你需要自己換算一下。我寫題的時候很容易在這里搞混所以后來干脆全部統(tǒng)一成 0 基閉區(qū)間統(tǒng)計。有了這個函數(shù)我們就能很快算出在時刻 T 之前一共出現(xiàn)了多少次不和諧事件。因為從 0 到 T 總共包含T 1個時刻其中countMatch(T)個是匹配時刻剩下的就是bad(T) (T 1) - countMatch(T)這個bad(T)隨著 T 增大一定是單調(diào)不減的因為新增一個時刻要么它是不和諧事件bad 加一要么它是匹配事件bad 保持不變。有了單調(diào)性就可以放心地使用二分答案來找第一個滿足bad(T) k的 T 了。3.3 二分上界的處理與邊界細節(jié)二分的時候左邊界自然是 0右邊界需要認真處理一下。如果不加思考直接設(shè)一個很大的數(shù)比如4e18不僅可能溢出還會增加二分次數(shù)。更好的做法是用倍增法先找一個可行的上界從 1 開始如果當(dāng)前右邊界還不夠就不斷翻倍直到bad(r) k。long long l 0, r 1; while (bad(r - 1) k) { r 1; }這里為什么用bad(r - 1)而不是bad(r)因為我們要找的是最小的 T 使得 bad(T) 已經(jīng)達到 k檢查r - 1是為了確定在進入?yún)^(qū)間[r/2, r]之前r - 1還沒達到目標。如果你用bad(r)判斷倒也不會錯只是會多倍增一次代碼里足夠小心就行。還有一種更直接的上界估計方法每周期不和諧次數(shù)是L - matchPos.size()平均下來大約每隔這么久會出現(xiàn)一次不和諧所以答案大概在k * L / (L - matchPos.size())附近。但這個估計在數(shù)據(jù)極端時會有偏差比如某些匹配事件集中在周期開頭導(dǎo)致前面的不和諧密度和后面不一樣所以還是倍增法最省心。我實際測試下來在 k 到 1e18 時倍增加二分總共也就多幾十次迭代完全不影響效率。二分內(nèi)部的countMatch如果 matchPos 數(shù)組很大可以提前把數(shù)組排序然后每次二分內(nèi)部再做一次upper_bound整體復(fù)雜度大概是 O(log(k) * log(|matchPos|))非常穩(wěn)定。4. 完整實現(xiàn)從公式到可以跑通的代碼4.1 數(shù)據(jù)結(jié)構(gòu)與重要變量設(shè)計在寫實現(xiàn)之前我先把整個程序分成了幾個清晰的階段讀入 n, m, k 和兩個數(shù)組 a, b。計算 g gcd(n, m)L n / g * m。建立 b 數(shù)組的顏色到下標列表的映射比如unordered_mapint, vectorint posB。遍歷 a 的下標 i對每種顏色 c a[i]拿到 posB[c] 里的所有下標 j過濾掉i % g ! j % g的組合。對通過過濾的組合解同余方程求出它們在第一個周期內(nèi)的對齊時刻 x0放進matchPos。對matchPos排序。二分答案。這里有一個點值得單獨說一下L n / g * m這個式子應(yīng)該先除后乘因為n * m可能爆long long而n / g一定是整數(shù)先除能有效降低溢出風(fēng)險。雖然最后 L 本身也可能非常大但至少我們在計算過程中盡量推遲溢出的發(fā)生。4.2 核心函數(shù)代碼講解擴展中國剩余定理的合并函數(shù)是整道題的地基我先把版本貼出來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是用來把擴展歐幾里得求出的特解調(diào)整到最小非負剩余防止后面的乘法得到負數(shù)結(jié)果。第二x (__int128)x * k % mod這一步必須注意乘法可能超過long long的范圍因為 x 和 k 理論上都能到 mod 的量級而 mod 又有可能是 1e18 量級這時候普通乘法直接 UB 給你看。第三最后算 lcm 和 r 的時候m1 * x也可能爆所以要轉(zhuǎn)成__int128再取模。__int128在競賽環(huán)境里基本都能用但如果你在某類不支持它的評測機上做項目就得自己寫快速乘不過競賽場景里我一般就直接用了。有了這個合并函數(shù)求解位置對 (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; // 無解 // 這里合并結(jié)果 M 應(yīng)該等于 lcm(n, m)也就是 L return r % L; // 把對齊時刻歸一到第一個周期 [0, L) }由于我們只關(guān)心每個匹配事件的第一個出現(xiàn)位置所以計算完以后對 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; }這個主流程跑出來的結(jié)果我拿隨機數(shù)據(jù)和小規(guī)模暴力對拍過邏輯上是自洽的。需要注意的是countMatch里的full * cnt兩個量都可能很大已經(jīng)超過long long的可能性是存在的。如果你擔(dān)心這個問題可以用__int128來保存計數(shù)值最后和 k 比較的時候再取出來。真正寫題的時候我一般會根據(jù)數(shù)據(jù)范圍決定要不要防護但代碼里最好還是加上一層畢竟這種地方一旦爆掉了調(diào)試起來非常痛苦。5. 實測中踩過的坑5.1 溢出問題lcm 和乘法爆 long long這個坑我基本上每次做擴展中國剩余定理相關(guān)的題都會遇到幾乎是必修課。比如 n 1e9m 1e9 且互質(zhì)L 1e18這時候full * cnt和(T - x0) / L 1這類表達式都很容易在中間步驟溢出。我在第一次寫這道題的時候二分內(nèi)部用的是最樸素的逐項統(tǒng)計方式for (ll x0 : matchPos) { if (T x0) match (T - x0) / L 1; }結(jié)果 match 本身是long long當(dāng) match 逼近 1e18 的時候再往上加 1沒問題但T - x0如果 T 也很大倒是還好。真正危險的是后來我為了追求效率改成了 full * cnt兩個數(shù)相乘直接爆。解決方案有三個一是全程__int128做中間量二是用long double粗略估計再配合特殊判斷三是用快速乘。我建議直接上__int128代碼可讀性最好性能損失也微乎其微。5.2 索引 0 基與 1 基帶來的“對不齊”錯誤很多周期類題目的描述里喜歡用“第 1 個位置”“第 1 秒”這樣的表述稍不注意就會把整個同余方程寫歪。我舉個例子如果題面說第 1 秒時第一盞燈顯示 a[1]那么寫成同余關(guān)系時你如果直接用t ≡ 1 (mod n)去套很可能就把 a 的第 1 個元素當(dāng)成了下標 0導(dǎo)致后半段所有對齊時刻全部錯位。我個人的處理辦法是在讀入階段就把所有數(shù)組變成 0 基同時把查詢也換算成 0 基時間。比如“第 k 個不和諧的時刻”如果從 1 開始計數(shù)而我們代碼里 bad(T) 統(tǒng)計的是閉區(qū)間 [0, T] 內(nèi)的不和諧事件數(shù)那么答案是bad(T) k最小的 T輸出的時候如果需要 1 基就輸出T 1。如果你堅持全程 1 基也不是不行但取模運算會多出一堆-1極度容易寫錯。這個坑我建議所有讀者自己動手推一遍拿 n 4, m 6a 和 b 都是小樣例手動列一下 0 基和 1 基的差別比看十篇文章都管用。5.3 答案上界估計錯誤導(dǎo)致二分死循環(huán)二分本身不太容易死循環(huán)但如果你的右邊界從一開始就比真實答案小那二分就會一直卡在右邊界上返回錯誤結(jié)果。我最初的版本用了r k * L這種粗暴估計結(jié)果有一個數(shù)據(jù)點 k 很大但 L 也很大的時候k * L直接溢出成負數(shù)右邊界變成-1二分直接原地去世。后來我改成倍增法之后就再也沒出過問題。倍增法的好處是不需要提前估算答案的量級它通過不斷翻倍把右邊界推到一個足夠大的點最多翻 60 次左右就覆蓋了整個long long范圍。配合左邊界 0二分次數(shù)穩(wěn)定在 60 次附近非常放心。5.4 匹配事件重復(fù)計數(shù)的問題如果你像我最開始那樣把所有滿足a[i] b[j]的位置對都往里塞不加以過濾或者去重可能會出現(xiàn)同一個初始時刻 x0 被多次收集。舉個例子如果數(shù)組 a 里有兩個位置顏色相同比如 a[1] a[3] c而 b 里也有對應(yīng)同色位置理論上它們會分別產(chǎn)生兩個不同的對齊時刻 x0 和 x0但如果兩個位置對最后解出來的 x0 恰好相等呢這種情況可能出現(xiàn)嗎仔細想想x0 由i mod n和j mod m唯一確定如果 x0 相等那么 i x0 mod nj x0 mod m也就是說位置對本身是唯一的。所以在真正合法的位置對里x0 不會重復(fù)。但如果你在過濾階段沒有做i % g j % g的判斷用 EXCRT 解出來可能返回同一個 r 嗎其實不會因為如果 (i, j) 不同r 在模 L 下也不同。但為了保險起見我在代碼里還是會對 matchPos 做一次 sort unique畢竟不怕一萬只怕萬一多一行代碼的成本可以忽略不計。6. 這套組合還能用在哪些題上6.1 識別“周期匹配 第 k 事件”的題型特征刷題刷多了之后你會發(fā)現(xiàn)很多題都有一個共同的骨架兩個周期事件可能相同也可能不同然后問第 k 次某種狀態(tài)發(fā)生在什么時候。比如兩個交通信號燈以不同周期循環(huán)問你第 k 次同時變綠兩個機器人以不同步長走路問你第 k 次踩到同一個格子。這類問題一旦出現(xiàn)數(shù)據(jù)范圍又很大基本就能鎖定是“Chinese Remainder 二分”的組合。識別這種題型的信號有題目中出現(xiàn)兩個不同周期的循環(huán)序列查詢是第 k 次某種事件而不是請你輸出某個周期的狀態(tài)k 的范圍比單獨一個序列的長度大很多事件是否發(fā)生取決于兩個序列某個位置的某種關(guān)系。遇到這種題第一步永遠是找公共周期 L第二步是把“事件”映射到 L 內(nèi)的有限個初始時刻第三步是二分答案。三步走完代碼基本就成型了。6.2 變體求第 k 次“匹配”而不是“不匹配”我們上面講的都是求第 k 次不和諧也就是匹配事件的反面。如果題目反過來問第 k 次匹配發(fā)生在什么時候思路完全一樣只是把判斷函數(shù)換成countMatch(T) k而已。因為匹配事件和之前一樣也是周期性的統(tǒng)計函數(shù)不需要變只需要把二分和閾值條件改一下。我在寫這道題的時候一開始把 bad 函數(shù)封裝得比較死后來發(fā)現(xiàn)如果換個判斷條件又要重新寫一個邏輯。所以我在項目里盡量把countMatch獨立出來讓 bad 只是它的一個薄包裝。這樣不管題目問的是匹配還是不匹配核心統(tǒng)計邏輯都能復(fù)用。6.3 EXCRT 作為通用工具的獨立價值最后想單獨說一句擴展中國剩余定理本身。它不只是這道題的一個零件在很多同余方程組相關(guān)的題目里都是核心工具。比如求某個數(shù)滿足若干個模數(shù)不互質(zhì)的余數(shù)條件或者求某些數(shù)列的最早相遇時刻都會用到這套 exgcd 合并方程的方法。我建議讀者把mergeEquation這個函數(shù)背熟它比普通 CRT 的適用范圍廣得多而且代碼量并沒有多多少。以后遇到“模數(shù)不互質(zhì)”的第一反應(yīng)就應(yīng)該是 EXCRT而不是轉(zhuǎn)過頭去試圖把數(shù)據(jù)拆成互質(zhì)的情況。我在實際編碼中還養(yǎng)成了一個習(xí)慣每次寫完 EXCRT 類型的代碼都會用一個小暴力對拍器驗證比如隨機生成幾個同余方程手動枚舉小范圍 x 檢查合并后的結(jié)果是否真的同時滿足所有方程。這個習(xí)慣幫我抓出了至少三次因為取模邊界寫錯導(dǎo)致的隱蔽 bug。雖然對拍會花幾分鐘時間但在這種數(shù)論代碼上幾分鐘的驗證往往能省下后期幾小時的調(diào)試時間。最后再分享一點個人體會這道題做完之后我對“周期性事件統(tǒng)計”這類題的理解提升了一個層次。很多看似是模擬的題目核心其實都在于你能不能看穿事件的重復(fù)結(jié)構(gòu)。兩盞吊燈的循環(huán)本質(zhì)上就是兩個模數(shù) n 和 m 驅(qū)動的狀態(tài)機整個系統(tǒng)每 lcm(n, m) 個時刻完全復(fù)刻一次。你能不能在第一個周期內(nèi)把事件的位置全部找出來能不能在第二個周期開始之后用數(shù)學(xué)方式“跳過”中間的重復(fù)決定了這道題是 O(n m) 還是 O(k) 的差距。我自己的建議是遇到這種題不要急著寫代碼先拿筆在草稿紙上列出同余方程組把合并過程和二分邊界寫清楚再動手。數(shù)論題最怕的不是思路難而是細節(jié)多一個符號錯位就能讓你 Debug 到懷疑人生。把 0 基時間、閉區(qū)間統(tǒng)計、先除后乘這三個習(xí)慣刻進肌肉記憶里這類題你也能穩(wěn)定拿下。