1. 從一道題說起因子鏈與數論直覺最近在準備藍橋杯國賽刷題時遇到一道很有意思的數論題叫“X的因子鏈”。題目大意是給定一個正整數X我們要構造一個盡可能長的序列序列的第一個數是1最后一個數是X并且序列中后一個數必須是前一個數的倍數。同時序列中除了1和X以外的所有數都必須是X的因子。問這樣的最長序列有多少條初看題目可能會有點懵。序列要長后一項是前一項的倍數中間項還得是X的因子……這聽起來有點像在X的因子集合里找一條“倍數關系”的路徑并且要盡可能長。直覺告訴我這肯定和X的質因數分解脫不了干系。數論題嘛尤其是藍橋杯國賽級別的往往不會讓你真的去暴力枚舉所有因子和排列背后一定有巧妙的數學原理可以大幅簡化計算。這道題的核心其實就是對“算術基本定理”和“線性篩質數”這兩個基礎但強大的工具的一次深度應用和思維體操。今天我就結合自己的解題過程把里面的門道掰開揉碎了講清楚你會發(fā)現看似復雜的組合問題最終會歸結為一個優(yōu)雅的排列數計算。2. 算術基本定理拆解問題的基石要理解“X的因子鏈”首先得徹底搞懂X的因子是怎么來的。這就不得不提數論的“基石”——算術基本定理。算術基本定理告訴我們任何一個大于1的自然數都可以唯一地分解成有限個質數的乘積。這里的“唯一”是指如果不考慮質因數的排列順序那么這種分解方式是唯一的。用公式表示就是X p1^a1 * p2^a2 * ... * pk^ak其中p1, p2, ..., pk是互不相同的質數a1, a2, ..., ak是正整數表示對應質因數的指數。這個定理為什么是基石因為它完全決定了X的所有因子。X的任意一個正因子d其質因數分解必然是這樣的形式d p1^b1 * p2^b2 * ... * pk^bk其中對于每一個i指數bi的取值范圍是0 bi ai。舉個例子假設X 12。分解質因數12 2^2 * 3^1。 那么12的所有因子1, 2, 3, 4, 6, 12就可以通過分配指數得到1 2^0 * 3^02 2^1 * 3^03 2^0 * 3^14 2^2 * 3^06 2^1 * 3^112 2^2 * 3^1看到這里你應該能發(fā)現因子和質因數指數向量(b1, b2, ..., bk)是一一對應的。這個對應關系是解決本題的關鍵?，F在回到我們的“因子鏈”問題。鏈的要求是1 d0, d1, d2, ..., dm X且d(i)是d(i-1)的倍數同時d1, ..., d(m-1)都是X的因子。倍數關系意味著什么如果d(i)是d(i-1)的倍數那么d(i) / d(i-1)是一個大于1的整數。從質因數分解的角度看這意味著在從d(i-1)到d(i)的過程中某些質因數的指數增加了至少增加1而其他質因數的指數保持不變或也增加。更關鍵的是由于鏈上的每個數都是X的因子所以它們的指數向量(b1, b2, ..., bk)都滿足0 bj aj。并且序列從(0,0,...,0)對應數字1開始到(a1, a2, ..., ak)對應數字X結束。每一步我們只能選擇某一個質因數pj將其指數bj增加1因為要保證后一個是前一個的倍數且增長的步長最小化才能讓鏈最長這里先埋個伏筆。于是整個“構造最長因子鏈”的問題被完美地轉化了我們有k種不同的“質因數球”第j種球有aj個。我們需要把這些球排成一列。排球的順序就對應了因子鏈增長的順序。每次拿到一個第j種球就意味著我們將X的因子中質因數pj的指數增加了1。這樣構造出來的序列其對應的數字序列一定是滿足題目要求的因子鏈并且鏈的長度是固定的m a1 a2 ... ak 1。這里的“1”是因為起點1全0指數也算一個。這個長度就是最長可能長度因為我們把X的所有質因數指數從0增長到滿額每一步只增長1這已經是最細致的增長方式了不可能更長了。所以第一個問題的答案最長因子鏈的長度L (a1 a2 ... ak) 1。3. 線性篩質數高效獲取質因數分解在將問題轉化為“排列質因數球”之后我們面臨一個更前置的、也是算法題中的經典問題如何對給定的X快速地進行質因數分解得到所有的pi和ai對于單次查詢我們當然可以用試除法從2遍歷到sqrt(X)。但題目往往會有多組測試數據或者X本身很大比如10^6甚至更大這時O(sqrt(X))的復雜度可能就吃不消了。藍橋杯對效率是有要求的這就需要我們提前進行預處理。這就是線性篩質數歐拉篩大顯身手的地方。線性篩可以在O(n)的時間復雜度內篩選出1到n之間的所有質數。但它的威力不止于此經過巧妙改造我們可以讓它同時求出每個數的最小質因數Least Prime Factor, LPF。有了最小質因數我們對任意數X進行質因數分解的復雜度就從O(sqrt(X))降到了O(log X)。讓我解釋一下這背后的原理和操作。3.1 標準線性篩歐拉篩的原理普通的埃氏篩時間復雜度是O(n log log n)核心思想是標記每個質數的倍數。但它有個問題一個合數會被它的所有質因子重復標記比如6會被2和3各標記一次。線性篩通過一個關鍵優(yōu)化保證了每個合數只被其最小質因數標記一次。算法步驟如下用代碼邏輯描述更清晰初始化一個布爾數組is_prime[0..n]全部為true一個空列表primes存放質數。從i 2遍歷到n a. 如果is_prime[i]為true則將i加入primes列表。 b. 遍歷已有的質數列表primes設當前質數為p - 計算next i * p。 - 如果next n跳出循環(huán)。 - 標記is_prime[next] false。 -關鍵判斷如果i % p 0則跳出內層循環(huán)。這保證了next這個合數是被其最小質因數p篩掉的。最后這個if (i % p 0) break;是精髓。因為i能被p整除說明p是i的最小質因數我們從小到大遍歷質數表。那么對于后續(xù)更大的質數pi * p的最小質因數依然是p而不是p。這個合數應該留給未來某個i此時i是i * p / p與p相乘時來標記以保證“最小質因數標記”的原則。3.2 改造以記錄最小質因數LPF為了加速質因數分解我們需要一個數組lpf[N]其中l(wèi)pf[x]存儲數字x的最小質因數。 在篩法的標記步驟中當我們確定next i * p將被篩掉時我們就知道了next的最小質因數是p。所以我們可以直接設置lpf[next] p。 對于質數i本身其最小質因數就是它自己所以lpf[i] i。改造后的核心代碼片段C風格如下const int N 1000000; // 根據數據范圍設定 vectorint primes; int lpf[N1]; bool is_prime[N1]; void linear_sieve(int n) { fill(is_prime, is_prime n 1, true); for (int i 2; i n; i) { if (is_prime[i]) { primes.push_back(i); lpf[i] i; // 質數的最小質因數是自身 } for (int p : primes) { long long next 1LL * i * p; if (next n) break; is_prime[next] false; lpf[next] p; // 記錄合數 next 的最小質因數是 p if (i % p 0) break; // 關鍵保證每個合數只被最小質因數篩一次 } } }3.3 利用LPF進行快速質因數分解有了lpf數組分解任意x (1 x N)就變得異常高效初始化一個空列表或映射factors用于存儲質因數及其指數。while (x 1): a. 取出p lpf[x]。 b. 在factors中將質因數p的計數加1。 c.x x / p。循環(huán)結束factors中就存儲了x的所有質因數及其指數。這個過程的時間復雜度是O(k)其中k是x的質因數個數重復的算多個。由于每次循環(huán)x至少除以2所以循環(huán)次數不超過log2(x)非?？?。實操心得在算法競賽中如果題目數據范圍明確比如X 10^6并且涉及大量數的質因數分解提前用線性篩預處理lpf數組是標準操作。這屬于典型的“空間換時間”并且這個空間開銷一個int數組通常是可接受的。自己實現一遍線性篩并理解if (i % p 0) break;這一行是掌握數論算法基礎的重要一步。4. 多重集排列數計算最長鏈的數目現在我們已經知道最長因子鏈的構造過程等價于將所有的“質因數球”一個多重集排成一列。那么第二個問題最長鏈的數目就等價于求這個多重集的全排列數。什么是多重集就是元素可以重復的集合。比如我們的質因數集合有a1個p1a2個p2...ak個pk。多重集的全排列公式是總排列數 (總球數)! / (每種球數量的階乘之積)即N (a1 a2 ... ak)! / (a1! * a2! * ... * ak!)這個公式直觀上很好理解如果所有球都不同排列數就是(總球數)!。但現在有a1個相同的p1球它們在所有排列中互換位置不會產生新的排列所以要除以a1!來消除這種重復。對其他種類的球也是如此。在我們的問題中總球數就是所有質因數的指數之和記作total a1 a2 ... ak。這正是鏈的長度L - 1。所以最長因子鏈的數目Ans total! / (a1! * a2! * ... * ak!)。4.1 如何計算這個可能巨大的數這里又有一個坑。total可能很大total!的結果是一個天文數字遠遠超出任何基本數據類型的范圍。題目通常會要求輸出結果對一個特定的數M取模比如M 1e97或2^64自然溢出。藍橋杯的這道題根據歷年風格很可能要求輸出具體數值不取模但數值會保證在long long64位整數范圍內。這就要求我們不能直接計算階乘然后相除因為中間結果會溢出。我們需要一種在計算過程中就能處理大數或者避免大數階乘的方法。方法一邊乘邊除利用整數除法由于最終答案一定是整數我們可以設計一個循環(huán)從1累乘到total但在乘的過程中盡可能早地除以分母中各ai!的因子。我們可以預處理出分母中所有需要被除掉的數即所有1到ai的每個數然后在對分子累乘時一旦當前乘積能被某個分母的因子整除就立即除。這需要維護一個分母因子的數組并不斷嘗試約分。方法二組合數學公式與遞推其實total! / (a1! * a2! * ... * ak!)這個式子有深刻的組合意義。它可以理解為有total個位置我們先從中選a1個位置放p1有C(total, a1)種選法然后從剩下的total - a1個位置中選a2個位置放p2有C(total - a1, a2)種選法依此類推。 根據乘法原理Ans C(total, a1) * C(total - a1, a2) * ... * C(ak, ak)其中C(n, m)是組合數。組合數C(n, m) n! / (m! * (n-m)!)。雖然也要算階乘但我們可以用遞推公式或預處理階乘與逆元在取模意義下的方式來高效計算。對于不取模、保證結果在long long內的情況我們可以用C(n, m) C(n-1, m-1) C(n-1, m)的遞推公式動態(tài)規(guī)劃計算一個較小的組合數表因為total不會特別大或者直接用乘法與除法交替計算單個組合數并注意使用long long防止中間溢出。4.2 一個完整的計算示例假設X 12 2^2 * 3^1。 則a12 (對應質數2), a21 (對應質數3)。total a1 a2 3。 最長鏈長度L total 1 4。 最長鏈數目Ans 3! / (2! * 1!) 6 / (2 * 1) 3。我們可以驗證一下。所有“質因數球”是{2, 2, 3}。 其所有排列為2, 2, 32, 3, 23, 2, 2每一種排列對應一條最長因子鏈。以排列2, 3, 2為例起始數字1指數向量 (0, 0)第一步拿到一個“2”球指數向量變?yōu)?(1, 0)對應數字 2^1 * 3^0 2第二步拿到一個“3”球指數向量變?yōu)?(1, 1)對應數字 2^1 * 3^1 6第三步拿到一個“2”球指數向量變?yōu)?(2, 1)對應數字 2^2 * 3^1 12 所以對應的因子鏈是1 - 2 - 6 - 12。另外兩種排列對應鏈1-2-4-12 和 1-3-6-12。正好是3條。注意事項在計算排列數時務必注意數據范圍和溢出問題。如果題目明確不取模要確保你的計算路徑無論是邊乘邊除還是遞推組合數中所有的中間結果和最終結果都在long long最大值約9e18范圍內。對于total較大的情況邊乘邊除需要精心設計約分順序否則中間乘積可能溢出。一個穩(wěn)妥的做法是將分子分母都分解質因數統計每個質因數的總指數然后直接計算這個質因數乘積這樣每一步都是乘法只要最終結果不溢出即可。5. 算法實現與細節(jié)雕琢理論清晰了接下來就是把思路轉化成代碼。這里我給出一個完整的、注重效率和魯棒性的C實現框架并逐一解釋關鍵細節(jié)。5.1 數據結構與預處理首先我們需要根據X的最大可能值比如題目給定的上限MAX_X來初始化線性篩。#include iostream #include vector #include map #include algorithm using namespace std; const int MAX_X 1000000; // 假設題目中X最大為1e6 vectorint primes; int lpf[MAX_X 1]; bool is_prime[MAX_X 1]; void init() { fill(is_prime, is_prime MAX_X 1, true); for (int i 2; i MAX_X; i) { if (is_prime[i]) { primes.push_back(i); lpf[i] i; } for (int p : primes) { long long next 1LL * i * p; if (next MAX_X) break; is_prime[next] false; lpf[next] p; if (i % p 0) break; } } }5.2 質因數分解函數利用lpf數組快速分解。// 返回一個映射key是質因數value是指數 mapint, int factorize(int x) { mapint, int factors; while (x 1) { int p lpf[x]; factors[p]; // 對應質因數指數加1 x / p; } return factors; }使用map可以自動按質因數大小排序方便后續(xù)處理雖然對本題計算來說順序無關。5.3 計算排列數不取模保證不溢出這里采用“邊乘邊除”的策略并假設最終答案在long long范圍內。我們需要計算total! / (a1! * a2! * ... * ak!)。 一個技巧是準備一個分母因子的列表然后對分子從1乘到total每乘一個數i就遍歷分母列表如果能整除某個分母因子d則i / d并將該d從列表中移除或標記為已使用。但這樣效率較低O(total * k)。更高效且不易出錯的方法是將分母的每個階乘展開成連續(xù)的整數然后與分子的連續(xù)整數進行“約分”。我們可以模擬一個分數乘法Ans 1for i from 1 to total:Ans * ifor 每個質因數種類j:while (aj 0 且 Ans % (aj的當前值) 0):Ans / ajaj--但這樣寫邏輯有點亂且aj被修改了。更好的實現是用一個數組denom存放所有需要被除掉的數即所有1,2,...,a1, 1,2,...,a2, ...。然后計算分子連乘時不斷與denom中的數約分。long long calculate_permutations(const mapint, int factors) { vectorint denom; // 存放所有分母的因子 int total 0; for (auto [p, cnt] : factors) { total cnt; for (int v 1; v cnt; v) { denom.push_back(v); // 將 cnt! 展開為 1,2,...,cnt } } long long ans 1; for (int numerator 1; numerator total; numerator) { ans * numerator; // 乘以分子的一個因子 // 嘗試用分母列表中的數約分ans for (int d : denom) { if (d 1 ans % d 0) { ans / d; d 1; // 該分母因子已被約掉標記為1 } } } // 理論上循環(huán)結束后denom中所有數都應被約分為1 return ans; }這個實現清晰且易于理解。時間復雜度是O(total * (total的質因數種類數))在total不大比如小于30時完全可行。這也是本題的隱含條件因為total是質因數指數和對于X 10^6total不會太大因為2^20就超過100萬了所以total最多20左右。5.4 主邏輯與完整代碼框架將以上部分組合起來。int main() { init(); // 預處理線性篩 int x; while (cin x) { // 假設有多組測試數據 if (x 1) { // 特殊情況1的因子只有1最長鏈就是 1 - 1長度為1數量為1 cout 1 1 endl; continue; } mapint, int factors factorize(x); int total 0; for (auto [p, cnt] : factors) { total cnt; } int length total 1; long long count calculate_permutations(factors); cout length count endl; } return 0; }5.5 邊界情況與測試X 1這是一個特例。1沒有質因數。按照定義因子鏈只有[1]長度為1數量為1。我們的質因數分解函數對x1會返回空映射total0length1但在計算排列數時分母和分子都是空積視為1所以count應該是1。需要在計算函數或主邏輯中單獨處理或者確保calculate_permutations對空輸入返回1。X 是質數假設X p則factors {p:1}total1length2。排列數計算1! / 1! 1。對應因子鏈只有一條1 - p。符合直覺。X 是質數的冪假設X p^k則factors {p:k}totalklengthk1。排列數計算k! / k! 1。這是因為所有“球”都相同只有一種排列方式。對應的最長鏈是唯一的1 - p - p^2 - ... - p^k。常規(guī)合數如前文的X12應輸出4 3。踩坑實錄在實現calculate_permutations時我最開始犯了一個錯誤。我試圖先計算分子total!和每個分母ai!然后相除。即使使用long long20!的值約為2.43e18已經接近long long的上限9.22e18。如果total再大一點或者先乘后除的順序不對中間結果就溢出了。所以“邊乘邊除”或者“質因數統計法”是必須的。另外對于X1的特例一定要處理否則在計算total和遍歷分母時會出錯。6. 思維延伸與舉一反三解決了具體的題目我們不妨把思維再拔高一點看看這個“因子鏈”模型和相關的數學工具還能用在什么地方。6.1 與格路問題的聯系“多重集排列”問題有一個經典的組合解釋從坐標原點(0,0,...,0)走到點(a1, a2, ..., ak)每次只能沿著某個坐標軸的正方向走一步即增加一個對應質因數的指數。問有多少種不同的路徑這其實就是我們因子鏈的數目。每一步的選擇增加哪個質因數的指數對應路徑中的一個決策。這樣的路徑數正是多重集排列數。這建立了數論問題和組合幾何問題的一個有趣橋梁。6.2 線性篩的更多應用我們這里只用線性篩來求最小質因數LPF。實際上線性篩是數論算法中的“瑞士軍刀”經過改造它可以同時求出很多積性函數的值例如歐拉函數 φ(n)表示小于等于n且與n互質的數的個數。莫比烏斯函數 μ(n)用于莫比烏斯反演。約數個數函數 d(n)n的正約數個數。約數和函數 σ(n)n的所有正約數之和。其核心思想是在篩出合數i * p時根據i和p是否互質即i % p 0是否成立利用積性函數的性質可以由已知的f(i)和f(p)推導出f(i * p)。掌握這個技巧就能在O(n)時間內預處理出大量數論函數的前綴和這在解決復雜的數論求和問題時威力巨大。6.3 關于“最長”的嚴格性證明在我們之前的分析中我們默認了“每一步只增加一個質因數的指數1”的鏈是最長的。這需要一個小證明來讓整個邏輯更嚴密。證明設X的質因數分解為p1^a1 * ... * pk^ak。對于任意一個滿足題意的因子鏈1 d0, d1, ..., dm X考慮每個數對應的指數向量(b1, ..., bk)。從d(i-1)到d(i)由于d(i)是d(i-1)的倍數所以對于每個j有b_j(i) b_j(i-1)。并且因為d(i)是X的因子所以b_j(i) aj。 從全0向量到全aj向量每個分量bj需要從0增長到aj至少需要aj次增長。而每次增長即鏈中向前一步最多只能讓所有bj中的某一個增加至少1實際上因為d(i)/d(i-1)是一個大于1的整數它至少包含一個質因數所以至少有一個bj增加了至少1。因此鏈的長度m從1開始算步數至少需要1 (a1 a2 ... ak)。而我們構造的“每次只增加一個質因數指數1”的鏈正好達到了這個下界因此它是最長的。這就嚴格證明了我們方法的正確性。6.4 如果問題變體允許中間項不是X的因子如果去掉“中間項必須是X的因子”這個條件只要求序列從1到X且后一項是前一項的倍數。那么最長鏈是什么樣的此時我們可以在中間插入一些不是X因子的數。例如X12鏈可以是1 - 2 - 4 - 8 - 12其中8不是12的因子。這樣鏈更長了嗎并沒有因為從4到8乘2從8到12乘1.5不是整數等等8到12是乘1.5不是整數倍哦這里錯了。重新考慮1-2-4-8-12檢查倍數關系2是1的2倍4是2的2倍8是4的2倍但12不是8的整數倍12/81.5。所以這個鏈不合法。實際上在只要求倍數關系的情況下最長鏈是每次乘以一個質數直到達到X的所有質因數。這等價于將X分解質因數后按任意順序逐個乘上這些質因數。這又回到了我們最初的“質因數球”模型只不過現在“球”可以重復使用因為乘的質數可以不是X的因子不對最終乘積要等于X所以乘的質數必須是X的質因數且總次數等于指數。所以最長鏈的長度依然是total 1鏈的數目依然是多重集排列數。結論是在這個問題中“中間項是X的因子”這個條件對于最長鏈的長度和數量并沒有增加額外的約束它只是確保了鏈上的所有數都在X的因子集合內這個性質。這是一個有趣的發(fā)現說明原題的條件設計得非常精巧既增加了題目的趣味性又沒有改變最優(yōu)化問題的數學本質。最后回顧整個解題過程從理解題意、轉化問題算術基本定理到設計高效算法獲取輸入線性篩再到運用組合數學計算答案最后考慮邊界和優(yōu)化這是一道非常經典的、考察綜合數論與組合思維的題目。它不要求高深的數學知識但需要對基礎概念有深刻的理解和靈活的應用能力。在平時練習時多問幾個“為什么”比如“為什么這樣是最長”“這個公式是怎么來的”并動手實現、測試邊界情況才能真正吃透這類題目在賽場上遇到變體也能游刃有余。 從因子鏈問題解析算術基本定理與線性篩質數的應用
1. 從一道題說起因子鏈與數論直覺最近在準備藍橋杯國賽刷題時遇到一道很有意思的數論題叫“X的因子鏈”。題目大意是給定一個正整數X我們要構造一個盡可能長的序列序列的第一個數是1最后一個數是X并且序列中后一個數必須是前一個數的倍數。同時序列中除了1和X以外的所有數都必須是X的因子。問這樣的最長序列有多少條初看題目可能會有點懵。序列要長后一項是前一項的倍數中間項還得是X的因子……這聽起來有點像在X的因子集合里找一條“倍數關系”的路徑并且要盡可能長。直覺告訴我這肯定和X的質因數分解脫不了干系。數論題嘛尤其是藍橋杯國賽級別的往往不會讓你真的去暴力枚舉所有因子和排列背后一定有巧妙的數學原理可以大幅簡化計算。這道題的核心其實就是對“算術基本定理”和“線性篩質數”這兩個基礎但強大的工具的一次深度應用和思維體操。今天我就結合自己的解題過程把里面的門道掰開揉碎了講清楚你會發(fā)現看似復雜的組合問題最終會歸結為一個優(yōu)雅的排列數計算。2. 算術基本定理拆解問題的基石要理解“X的因子鏈”首先得徹底搞懂X的因子是怎么來的。這就不得不提數論的“基石”——算術基本定理。算術基本定理告訴我們任何一個大于1的自然數都可以唯一地分解成有限個質數的乘積。這里的“唯一”是指如果不考慮質因數的排列順序那么這種分解方式是唯一的。用公式表示就是X p1^a1 * p2^a2 * ... * pk^ak其中p1, p2, ..., pk是互不相同的質數a1, a2, ..., ak是正整數表示對應質因數的指數。這個定理為什么是基石因為它完全決定了X的所有因子。X的任意一個正因子d其質因數分解必然是這樣的形式d p1^b1 * p2^b2 * ... * pk^bk其中對于每一個i指數bi的取值范圍是0 bi ai。舉個例子假設X 12。分解質因數12 2^2 * 3^1。 那么12的所有因子1, 2, 3, 4, 6, 12就可以通過分配指數得到1 2^0 * 3^02 2^1 * 3^03 2^0 * 3^14 2^2 * 3^06 2^1 * 3^112 2^2 * 3^1看到這里你應該能發(fā)現因子和質因數指數向量(b1, b2, ..., bk)是一一對應的。這個對應關系是解決本題的關鍵?，F在回到我們的“因子鏈”問題。鏈的要求是1 d0, d1, d2, ..., dm X且d(i)是d(i-1)的倍數同時d1, ..., d(m-1)都是X的因子。倍數關系意味著什么如果d(i)是d(i-1)的倍數那么d(i) / d(i-1)是一個大于1的整數。從質因數分解的角度看這意味著在從d(i-1)到d(i)的過程中某些質因數的指數增加了至少增加1而其他質因數的指數保持不變或也增加。更關鍵的是由于鏈上的每個數都是X的因子所以它們的指數向量(b1, b2, ..., bk)都滿足0 bj aj。并且序列從(0,0,...,0)對應數字1開始到(a1, a2, ..., ak)對應數字X結束。每一步我們只能選擇某一個質因數pj將其指數bj增加1因為要保證后一個是前一個的倍數且增長的步長最小化才能讓鏈最長這里先埋個伏筆。于是整個“構造最長因子鏈”的問題被完美地轉化了我們有k種不同的“質因數球”第j種球有aj個。我們需要把這些球排成一列。排球的順序就對應了因子鏈增長的順序。每次拿到一個第j種球就意味著我們將X的因子中質因數pj的指數增加了1。這樣構造出來的序列其對應的數字序列一定是滿足題目要求的因子鏈并且鏈的長度是固定的m a1 a2 ... ak 1。這里的“1”是因為起點1全0指數也算一個。這個長度就是最長可能長度因為我們把X的所有質因數指數從0增長到滿額每一步只增長1這已經是最細致的增長方式了不可能更長了。所以第一個問題的答案最長因子鏈的長度L (a1 a2 ... ak) 1。3. 線性篩質數高效獲取質因數分解在將問題轉化為“排列質因數球”之后我們面臨一個更前置的、也是算法題中的經典問題如何對給定的X快速地進行質因數分解得到所有的pi和ai對于單次查詢我們當然可以用試除法從2遍歷到sqrt(X)。但題目往往會有多組測試數據或者X本身很大比如10^6甚至更大這時O(sqrt(X))的復雜度可能就吃不消了。藍橋杯對效率是有要求的這就需要我們提前進行預處理。這就是線性篩質數歐拉篩大顯身手的地方。線性篩可以在O(n)的時間復雜度內篩選出1到n之間的所有質數。但它的威力不止于此經過巧妙改造我們可以讓它同時求出每個數的最小質因數Least Prime Factor, LPF。有了最小質因數我們對任意數X進行質因數分解的復雜度就從O(sqrt(X))降到了O(log X)。讓我解釋一下這背后的原理和操作。3.1 標準線性篩歐拉篩的原理普通的埃氏篩時間復雜度是O(n log log n)核心思想是標記每個質數的倍數。但它有個問題一個合數會被它的所有質因子重復標記比如6會被2和3各標記一次。線性篩通過一個關鍵優(yōu)化保證了每個合數只被其最小質因數標記一次。算法步驟如下用代碼邏輯描述更清晰初始化一個布爾數組is_prime[0..n]全部為true一個空列表primes存放質數。從i 2遍歷到n a. 如果is_prime[i]為true則將i加入primes列表。 b. 遍歷已有的質數列表primes設當前質數為p - 計算next i * p。 - 如果next n跳出循環(huán)。 - 標記is_prime[next] false。 -關鍵判斷如果i % p 0則跳出內層循環(huán)。這保證了next這個合數是被其最小質因數p篩掉的。最后這個if (i % p 0) break;是精髓。因為i能被p整除說明p是i的最小質因數我們從小到大遍歷質數表。那么對于后續(xù)更大的質數pi * p的最小質因數依然是p而不是p。這個合數應該留給未來某個i此時i是i * p / p與p相乘時來標記以保證“最小質因數標記”的原則。3.2 改造以記錄最小質因數LPF為了加速質因數分解我們需要一個數組lpf[N]其中l(wèi)pf[x]存儲數字x的最小質因數。 在篩法的標記步驟中當我們確定next i * p將被篩掉時我們就知道了next的最小質因數是p。所以我們可以直接設置lpf[next] p。 對于質數i本身其最小質因數就是它自己所以lpf[i] i。改造后的核心代碼片段C風格如下const int N 1000000; // 根據數據范圍設定 vectorint primes; int lpf[N1]; bool is_prime[N1]; void linear_sieve(int n) { fill(is_prime, is_prime n 1, true); for (int i 2; i n; i) { if (is_prime[i]) { primes.push_back(i); lpf[i] i; // 質數的最小質因數是自身 } for (int p : primes) { long long next 1LL * i * p; if (next n) break; is_prime[next] false; lpf[next] p; // 記錄合數 next 的最小質因數是 p if (i % p 0) break; // 關鍵保證每個合數只被最小質因數篩一次 } } }3.3 利用LPF進行快速質因數分解有了lpf數組分解任意x (1 x N)就變得異常高效初始化一個空列表或映射factors用于存儲質因數及其指數。while (x 1): a. 取出p lpf[x]。 b. 在factors中將質因數p的計數加1。 c.x x / p。循環(huán)結束factors中就存儲了x的所有質因數及其指數。這個過程的時間復雜度是O(k)其中k是x的質因數個數重復的算多個。由于每次循環(huán)x至少除以2所以循環(huán)次數不超過log2(x)非?？?。實操心得在算法競賽中如果題目數據范圍明確比如X 10^6并且涉及大量數的質因數分解提前用線性篩預處理lpf數組是標準操作。這屬于典型的“空間換時間”并且這個空間開銷一個int數組通常是可接受的。自己實現一遍線性篩并理解if (i % p 0) break;這一行是掌握數論算法基礎的重要一步。4. 多重集排列數計算最長鏈的數目現在我們已經知道最長因子鏈的構造過程等價于將所有的“質因數球”一個多重集排成一列。那么第二個問題最長鏈的數目就等價于求這個多重集的全排列數。什么是多重集就是元素可以重復的集合。比如我們的質因數集合有a1個p1a2個p2...ak個pk。多重集的全排列公式是總排列數 (總球數)! / (每種球數量的階乘之積)即N (a1 a2 ... ak)! / (a1! * a2! * ... * ak!)這個公式直觀上很好理解如果所有球都不同排列數就是(總球數)!。但現在有a1個相同的p1球它們在所有排列中互換位置不會產生新的排列所以要除以a1!來消除這種重復。對其他種類的球也是如此。在我們的問題中總球數就是所有質因數的指數之和記作total a1 a2 ... ak。這正是鏈的長度L - 1。所以最長因子鏈的數目Ans total! / (a1! * a2! * ... * ak!)。4.1 如何計算這個可能巨大的數這里又有一個坑。total可能很大total!的結果是一個天文數字遠遠超出任何基本數據類型的范圍。題目通常會要求輸出結果對一個特定的數M取模比如M 1e97或2^64自然溢出。藍橋杯的這道題根據歷年風格很可能要求輸出具體數值不取模但數值會保證在long long64位整數范圍內。這就要求我們不能直接計算階乘然后相除因為中間結果會溢出。我們需要一種在計算過程中就能處理大數或者避免大數階乘的方法。方法一邊乘邊除利用整數除法由于最終答案一定是整數我們可以設計一個循環(huán)從1累乘到total但在乘的過程中盡可能早地除以分母中各ai!的因子。我們可以預處理出分母中所有需要被除掉的數即所有1到ai的每個數然后在對分子累乘時一旦當前乘積能被某個分母的因子整除就立即除。這需要維護一個分母因子的數組并不斷嘗試約分。方法二組合數學公式與遞推其實total! / (a1! * a2! * ... * ak!)這個式子有深刻的組合意義。它可以理解為有total個位置我們先從中選a1個位置放p1有C(total, a1)種選法然后從剩下的total - a1個位置中選a2個位置放p2有C(total - a1, a2)種選法依此類推。 根據乘法原理Ans C(total, a1) * C(total - a1, a2) * ... * C(ak, ak)其中C(n, m)是組合數。組合數C(n, m) n! / (m! * (n-m)!)。雖然也要算階乘但我們可以用遞推公式或預處理階乘與逆元在取模意義下的方式來高效計算。對于不取模、保證結果在long long內的情況我們可以用C(n, m) C(n-1, m-1) C(n-1, m)的遞推公式動態(tài)規(guī)劃計算一個較小的組合數表因為total不會特別大或者直接用乘法與除法交替計算單個組合數并注意使用long long防止中間溢出。4.2 一個完整的計算示例假設X 12 2^2 * 3^1。 則a12 (對應質數2), a21 (對應質數3)。total a1 a2 3。 最長鏈長度L total 1 4。 最長鏈數目Ans 3! / (2! * 1!) 6 / (2 * 1) 3。我們可以驗證一下。所有“質因數球”是{2, 2, 3}。 其所有排列為2, 2, 32, 3, 23, 2, 2每一種排列對應一條最長因子鏈。以排列2, 3, 2為例起始數字1指數向量 (0, 0)第一步拿到一個“2”球指數向量變?yōu)?(1, 0)對應數字 2^1 * 3^0 2第二步拿到一個“3”球指數向量變?yōu)?(1, 1)對應數字 2^1 * 3^1 6第三步拿到一個“2”球指數向量變?yōu)?(2, 1)對應數字 2^2 * 3^1 12 所以對應的因子鏈是1 - 2 - 6 - 12。另外兩種排列對應鏈1-2-4-12 和 1-3-6-12。正好是3條。注意事項在計算排列數時務必注意數據范圍和溢出問題。如果題目明確不取模要確保你的計算路徑無論是邊乘邊除還是遞推組合數中所有的中間結果和最終結果都在long long最大值約9e18范圍內。對于total較大的情況邊乘邊除需要精心設計約分順序否則中間乘積可能溢出。一個穩(wěn)妥的做法是將分子分母都分解質因數統計每個質因數的總指數然后直接計算這個質因數乘積這樣每一步都是乘法只要最終結果不溢出即可。5. 算法實現與細節(jié)雕琢理論清晰了接下來就是把思路轉化成代碼。這里我給出一個完整的、注重效率和魯棒性的C實現框架并逐一解釋關鍵細節(jié)。5.1 數據結構與預處理首先我們需要根據X的最大可能值比如題目給定的上限MAX_X來初始化線性篩。#include iostream #include vector #include map #include algorithm using namespace std; const int MAX_X 1000000; // 假設題目中X最大為1e6 vectorint primes; int lpf[MAX_X 1]; bool is_prime[MAX_X 1]; void init() { fill(is_prime, is_prime MAX_X 1, true); for (int i 2; i MAX_X; i) { if (is_prime[i]) { primes.push_back(i); lpf[i] i; } for (int p : primes) { long long next 1LL * i * p; if (next MAX_X) break; is_prime[next] false; lpf[next] p; if (i % p 0) break; } } }5.2 質因數分解函數利用lpf數組快速分解。// 返回一個映射key是質因數value是指數 mapint, int factorize(int x) { mapint, int factors; while (x 1) { int p lpf[x]; factors[p]; // 對應質因數指數加1 x / p; } return factors; }使用map可以自動按質因數大小排序方便后續(xù)處理雖然對本題計算來說順序無關。5.3 計算排列數不取模保證不溢出這里采用“邊乘邊除”的策略并假設最終答案在long long范圍內。我們需要計算total! / (a1! * a2! * ... * ak!)。 一個技巧是準備一個分母因子的列表然后對分子從1乘到total每乘一個數i就遍歷分母列表如果能整除某個分母因子d則i / d并將該d從列表中移除或標記為已使用。但這樣效率較低O(total * k)。更高效且不易出錯的方法是將分母的每個階乘展開成連續(xù)的整數然后與分子的連續(xù)整數進行“約分”。我們可以模擬一個分數乘法Ans 1for i from 1 to total:Ans * ifor 每個質因數種類j:while (aj 0 且 Ans % (aj的當前值) 0):Ans / ajaj--但這樣寫邏輯有點亂且aj被修改了。更好的實現是用一個數組denom存放所有需要被除掉的數即所有1,2,...,a1, 1,2,...,a2, ...。然后計算分子連乘時不斷與denom中的數約分。long long calculate_permutations(const mapint, int factors) { vectorint denom; // 存放所有分母的因子 int total 0; for (auto [p, cnt] : factors) { total cnt; for (int v 1; v cnt; v) { denom.push_back(v); // 將 cnt! 展開為 1,2,...,cnt } } long long ans 1; for (int numerator 1; numerator total; numerator) { ans * numerator; // 乘以分子的一個因子 // 嘗試用分母列表中的數約分ans for (int d : denom) { if (d 1 ans % d 0) { ans / d; d 1; // 該分母因子已被約掉標記為1 } } } // 理論上循環(huán)結束后denom中所有數都應被約分為1 return ans; }這個實現清晰且易于理解。時間復雜度是O(total * (total的質因數種類數))在total不大比如小于30時完全可行。這也是本題的隱含條件因為total是質因數指數和對于X 10^6total不會太大因為2^20就超過100萬了所以total最多20左右。5.4 主邏輯與完整代碼框架將以上部分組合起來。int main() { init(); // 預處理線性篩 int x; while (cin x) { // 假設有多組測試數據 if (x 1) { // 特殊情況1的因子只有1最長鏈就是 1 - 1長度為1數量為1 cout 1 1 endl; continue; } mapint, int factors factorize(x); int total 0; for (auto [p, cnt] : factors) { total cnt; } int length total 1; long long count calculate_permutations(factors); cout length count endl; } return 0; }5.5 邊界情況與測試X 1這是一個特例。1沒有質因數。按照定義因子鏈只有[1]長度為1數量為1。我們的質因數分解函數對x1會返回空映射total0length1但在計算排列數時分母和分子都是空積視為1所以count應該是1。需要在計算函數或主邏輯中單獨處理或者確保calculate_permutations對空輸入返回1。X 是質數假設X p則factors {p:1}total1length2。排列數計算1! / 1! 1。對應因子鏈只有一條1 - p。符合直覺。X 是質數的冪假設X p^k則factors {p:k}totalklengthk1。排列數計算k! / k! 1。這是因為所有“球”都相同只有一種排列方式。對應的最長鏈是唯一的1 - p - p^2 - ... - p^k。常規(guī)合數如前文的X12應輸出4 3。踩坑實錄在實現calculate_permutations時我最開始犯了一個錯誤。我試圖先計算分子total!和每個分母ai!然后相除。即使使用long long20!的值約為2.43e18已經接近long long的上限9.22e18。如果total再大一點或者先乘后除的順序不對中間結果就溢出了。所以“邊乘邊除”或者“質因數統計法”是必須的。另外對于X1的特例一定要處理否則在計算total和遍歷分母時會出錯。6. 思維延伸與舉一反三解決了具體的題目我們不妨把思維再拔高一點看看這個“因子鏈”模型和相關的數學工具還能用在什么地方。6.1 與格路問題的聯系“多重集排列”問題有一個經典的組合解釋從坐標原點(0,0,...,0)走到點(a1, a2, ..., ak)每次只能沿著某個坐標軸的正方向走一步即增加一個對應質因數的指數。問有多少種不同的路徑這其實就是我們因子鏈的數目。每一步的選擇增加哪個質因數的指數對應路徑中的一個決策。這樣的路徑數正是多重集排列數。這建立了數論問題和組合幾何問題的一個有趣橋梁。6.2 線性篩的更多應用我們這里只用線性篩來求最小質因數LPF。實際上線性篩是數論算法中的“瑞士軍刀”經過改造它可以同時求出很多積性函數的值例如歐拉函數 φ(n)表示小于等于n且與n互質的數的個數。莫比烏斯函數 μ(n)用于莫比烏斯反演。約數個數函數 d(n)n的正約數個數。約數和函數 σ(n)n的所有正約數之和。其核心思想是在篩出合數i * p時根據i和p是否互質即i % p 0是否成立利用積性函數的性質可以由已知的f(i)和f(p)推導出f(i * p)。掌握這個技巧就能在O(n)時間內預處理出大量數論函數的前綴和這在解決復雜的數論求和問題時威力巨大。6.3 關于“最長”的嚴格性證明在我們之前的分析中我們默認了“每一步只增加一個質因數的指數1”的鏈是最長的。這需要一個小證明來讓整個邏輯更嚴密。證明設X的質因數分解為p1^a1 * ... * pk^ak。對于任意一個滿足題意的因子鏈1 d0, d1, ..., dm X考慮每個數對應的指數向量(b1, ..., bk)。從d(i-1)到d(i)由于d(i)是d(i-1)的倍數所以對于每個j有b_j(i) b_j(i-1)。并且因為d(i)是X的因子所以b_j(i) aj。 從全0向量到全aj向量每個分量bj需要從0增長到aj至少需要aj次增長。而每次增長即鏈中向前一步最多只能讓所有bj中的某一個增加至少1實際上因為d(i)/d(i-1)是一個大于1的整數它至少包含一個質因數所以至少有一個bj增加了至少1。因此鏈的長度m從1開始算步數至少需要1 (a1 a2 ... ak)。而我們構造的“每次只增加一個質因數指數1”的鏈正好達到了這個下界因此它是最長的。這就嚴格證明了我們方法的正確性。6.4 如果問題變體允許中間項不是X的因子如果去掉“中間項必須是X的因子”這個條件只要求序列從1到X且后一項是前一項的倍數。那么最長鏈是什么樣的此時我們可以在中間插入一些不是X因子的數。例如X12鏈可以是1 - 2 - 4 - 8 - 12其中8不是12的因子。這樣鏈更長了嗎并沒有因為從4到8乘2從8到12乘1.5不是整數等等8到12是乘1.5不是整數倍哦這里錯了。重新考慮1-2-4-8-12檢查倍數關系2是1的2倍4是2的2倍8是4的2倍但12不是8的整數倍12/81.5。所以這個鏈不合法。實際上在只要求倍數關系的情況下最長鏈是每次乘以一個質數直到達到X的所有質因數。這等價于將X分解質因數后按任意順序逐個乘上這些質因數。這又回到了我們最初的“質因數球”模型只不過現在“球”可以重復使用因為乘的質數可以不是X的因子不對最終乘積要等于X所以乘的質數必須是X的質因數且總次數等于指數。所以最長鏈的長度依然是total 1鏈的數目依然是多重集排列數。結論是在這個問題中“中間項是X的因子”這個條件對于最長鏈的長度和數量并沒有增加額外的約束它只是確保了鏈上的所有數都在X的因子集合內這個性質。這是一個有趣的發(fā)現說明原題的條件設計得非常精巧既增加了題目的趣味性又沒有改變最優(yōu)化問題的數學本質。最后回顧整個解題過程從理解題意、轉化問題算術基本定理到設計高效算法獲取輸入線性篩再到運用組合數學計算答案最后考慮邊界和優(yōu)化這是一道非常經典的、考察綜合數論與組合思維的題目。它不要求高深的數學知識但需要對基礎概念有深刻的理解和靈活的應用能力。在平時練習時多問幾個“為什么”比如“為什么這樣是最長”“這個公式是怎么來的”并動手實現、測試邊界情況才能真正吃透這類題目在賽場上遇到變體也能游刃有余。