1. 項目概述從一道模板題看約數(shù)問題的核心解法在算法競賽和日常編程中處理整數(shù)的約數(shù)因數(shù)是一個高頻出現(xiàn)的基礎(chǔ)問題。無論是判斷質(zhì)數(shù)、分解質(zhì)因數(shù)還是解決更復(fù)雜的數(shù)論問題都離不開對約數(shù)性質(zhì)的深入理解和高效計算。AcWing 870題“約數(shù)個數(shù)”正是這樣一個經(jīng)典的“模板題”。它不要求你輸出所有約數(shù)而是要求計算一個數(shù)的約數(shù)總個數(shù)。這看似簡單但直接遍歷1到N判斷能否整除的暴力方法其時間復(fù)雜度為O(N)當N很大時例如10^9甚至10^12是完全不可行的。這道題的精髓在于它引導(dǎo)我們利用算術(shù)基本定理將求約數(shù)個數(shù)的問題轉(zhuǎn)化為一個基于質(zhì)因數(shù)分解的公式計算問題從而將復(fù)雜度降低到O(√N)。掌握這個模板就意味著你掌握了解決一大類約數(shù)相關(guān)問題的鑰匙。本文將深入拆解這道題的數(shù)學(xué)原理、C實現(xiàn)細節(jié)、常見變形以及在實際編碼中的避坑技巧讓你不僅會做這道題更能透徹理解其背后的思想并應(yīng)用到更廣泛的場景中。2. 核心思路與數(shù)學(xué)原理拆解2.1 為什么暴力枚舉行不通面對“求N的約數(shù)個數(shù)”這個問題最直觀的想法是從1循環(huán)到N逐個判斷是否能整除N。對于較小的N比如小于10^6這種方法勉強可用。但在算法題常見的約束下N的范圍動輒達到10^9循環(huán)10億次顯然會超時Time Limit Exceeded。更極端的情況如果N接近10^12暴力枚舉更是遙不可及。因此我們必須尋找更優(yōu)的數(shù)學(xué)方法。2.2 算術(shù)基本定理與約數(shù)個數(shù)公式這里就需要請出數(shù)論中的基石——算術(shù)基本定理。該定理指出任何一個大于1的自然數(shù)N都可以唯一地分解成有限個質(zhì)數(shù)的乘積。 即N p1^α1 * p2^α2 * ... * pk^αk其中p1, p2, ..., pk 是互不相同的質(zhì)數(shù)α1, α2, ..., αk 是正整數(shù)。這個分解式是理解約數(shù)個數(shù)的關(guān)鍵。N的任何一個約數(shù)d必然是由N的這些質(zhì)因子以不大于其指數(shù)的冪次組合而成。 例如假設(shè)N 2^3 * 3^2 72。那么它的一個約數(shù)d 2^1 * 3^2 18。可以看到d中質(zhì)因子2的指數(shù)1取自原數(shù)N中指數(shù)3的可能取值0, 1, 2, 3質(zhì)因子3的指數(shù)2取自原數(shù)N中指數(shù)2的可能取值0, 1, 2。由此我們可以推導(dǎo)出約數(shù)個數(shù)的計算公式對于N p1^α1 * p2^α2 * ... * pk^αk它的約數(shù)總個數(shù)為f(N) (α1 1) * (α2 1) * ... * (αk 1)公式解釋對于每一個質(zhì)因子pi在構(gòu)成約數(shù)時它的指數(shù)可以有(αi 1)種選擇即0, 1, 2, ..., αi。所有質(zhì)因子指數(shù)的選擇相互獨立根據(jù)乘法原理總的組合數(shù)就是各個(αi 1)的乘積。以N72為例72 2^3 * 3^2約數(shù)個數(shù) (3 1) * (2 1) 4 * 3 12。 我們可以列舉驗證72的約數(shù)有 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72正好12個。2.3 算法流程設(shè)計基于以上公式我們的算法流程變得清晰質(zhì)因數(shù)分解對給定的整數(shù)N進行質(zhì)因數(shù)分解得到所有質(zhì)因子pi及其對應(yīng)的指數(shù)αi。應(yīng)用公式計算遍歷分解結(jié)果將所有(αi 1)相乘得到的積就是約數(shù)的總個數(shù)。問題的核心和難點轉(zhuǎn)移到了如何高效地對一個整數(shù)進行質(zhì)因數(shù)分解。3. 核心細節(jié)解析與C實現(xiàn)要點3.1 高效的質(zhì)因數(shù)分解方法質(zhì)因數(shù)分解最常用的方法是試除法。但并非從2遍歷到N而是利用一個關(guān)鍵性質(zhì)如果N是一個合數(shù)那么它必然有一個不大于√N的質(zhì)因子。因此我們只需要用i從2遍歷到√N即i * i N。每當N % i 0說明i是N的一個質(zhì)因子為什么此時i一定是質(zhì)數(shù)因為我們在循環(huán)中從小到大嘗試如果i是合數(shù)它早就會被它的質(zhì)因子整除從而在輪到它之前N中對應(yīng)的質(zhì)因子已經(jīng)被除干凈了。接著我們用一個循環(huán)while (N % i 0)來除盡N中所有的i因子并統(tǒng)計次數(shù)s。將質(zhì)因子i和指數(shù)s記錄下來。循環(huán)結(jié)束后如果剩下的N 1那么此時的N本身就是一個大于√N的質(zhì)因子其指數(shù)為1。這個算法的時間復(fù)雜度是O(√N)比暴力枚舉的O(N)快了幾個數(shù)量級。注意在代碼中i需要聲明為long long類型因為當N很大時i * i可能會超出int的范圍導(dǎo)致溢出。這是一個非常容易忽略的細節(jié)。3.2 數(shù)據(jù)結(jié)構(gòu)選擇如何存儲質(zhì)因數(shù)分解結(jié)果我們需要存儲每個質(zhì)因子及其對應(yīng)的指數(shù)。在C中有兩種常見選擇vectorpairint, int清晰直觀pair的first存質(zhì)因子second存指數(shù)。unordered_mapint, int利用哈希表鍵(Key)為質(zhì)因子值(Value)為指數(shù)。它的好處是如果后續(xù)需要對多個數(shù)進行質(zhì)因數(shù)分解并合并例如求多個數(shù)乘積的約數(shù)個數(shù)使用map合并指數(shù)會非常方便。對于本題單個數(shù)兩者皆可。為了清晰展示原理我們先用vectorpairint, int。3.3 代碼實現(xiàn)與逐行解析以下是AcWing 870題的核心解法實現(xiàn)#include iostream #include vector #include unordered_map using namespace std; int main() { int n; cin n; unordered_mapint, int primes; // 使用哈希表存儲質(zhì)因子和指數(shù) while (n -- ) { int x; cin x; // 質(zhì)因數(shù)分解 x for (int i 2; i x / i; i ) { // 試除法遍歷到 sqrt(x) while (x % i 0) { x / i; primes[i] ; // 對應(yīng)質(zhì)因子指數(shù)加1 } } if (x 1) primes[x] ; // 處理剩余的大于 sqrt(x) 的質(zhì)因子 } long long res 1; // 結(jié)果可能很大用 long long 存儲 const int MOD 1e9 7; // 題目要求的取模值 for (auto prime : primes) { res res * (prime.second 1) % MOD; // 應(yīng)用公式(α_i 1) 連乘 } cout res endl; return 0; }代碼關(guān)鍵點解析for (int i 2; i x / i; i )這是試除法的核心循環(huán)條件。用i x / i代替i * i x是為了防止i * i溢出盡管本題x是int但這是一個好習(xí)慣。while (x % i 0)這個內(nèi)層循環(huán)用于除盡當前質(zhì)因子i并同時在primes[i]中累加指數(shù)。if (x 1) primes[x] ;循環(huán)結(jié)束后如果x大于1那么它一定是原始x的一個大于其平方根的質(zhì)因子且指數(shù)為1。long long res 1;最終結(jié)果是指數(shù)加一的連乘積這個數(shù)可能非常大必須用long long類型存儲并在計算過程中及時取模防止溢出。res res * (prime.second 1) % MOD;遍歷哈希表應(yīng)用約數(shù)個數(shù)公式并同時取模。4. 模板的擴展與常見問題剖析4.1 模板的通用性上述代碼不僅僅能解決“求一個數(shù)約數(shù)個數(shù)”的問題它是一個質(zhì)因數(shù)分解公式應(yīng)用的通用框架。稍作修改可以解決一系列衍生問題求約數(shù)之和約數(shù)之和公式為S(N) (p1^0 p1^1 ... p1^α1) * ... * (pk^0 pk^1 ... pk^αk)。在分解質(zhì)因數(shù)后計算每個括號內(nèi)的等比數(shù)列和可用快速冪加速再連乘即可。求多個數(shù)乘積的約數(shù)個數(shù)/和這是AcWing 871題的內(nèi)容。只需對每個輸入的數(shù)分別進行質(zhì)因數(shù)分解并將所有分解結(jié)果合并到同一個哈希表里指數(shù)相加然后再對合并后的質(zhì)因數(shù)結(jié)果套用公式。判斷約數(shù)個數(shù)是否為奇數(shù)約數(shù)個數(shù)為奇數(shù)意味著公式(α11)*...*(αk1)為奇數(shù)即每個(αi1)都是奇數(shù)所以每個αi必須是偶數(shù)。這意味著原數(shù)N必須是一個完全平方數(shù)。這是一個非常有用的小結(jié)論。4.2 常見“坑點”與調(diào)試技巧溢出問題中間計算溢出在試除法循環(huán)中使用i * i n判斷時如果i是inti*i可能溢出。更安全的寫法是i n / i。結(jié)果溢出約數(shù)個數(shù)可能非常大即使對1e97取模連乘過程中也可能溢出int。務(wù)必使用long long類型存儲中間結(jié)果res并在每次乘法后立即取模。時間復(fù)雜度誤判試除法復(fù)雜度是 O(√N)對于單個10^9級別的數(shù)是很快的。但如果題目要求處理10^5個這樣的數(shù)總復(fù)雜度就是10^5 * √(10^9) ≈ 10^8可能處于超時的邊緣。這時需要考慮更優(yōu)的預(yù)處理如線性篩法或數(shù)學(xué)優(yōu)化。特殊輸入的處理N 11的質(zhì)因數(shù)分解是空的根據(jù)公式空乘積定義為1所以1的約數(shù)個數(shù)是1約數(shù)只有它本身。我們的算法中primes為空res初始為1輸出正確。大質(zhì)數(shù)輸入例如N 10^97本身是個質(zhì)數(shù)。算法會從2遍歷到√N都沒有找到因子最后x 1分支會將其記錄為質(zhì)因子指數(shù)為1。結(jié)果(11)2正確。unordered_map與map的選擇unordered_map基于哈希表平均查找插入是O(1)map基于紅黑樹是O(log n)。在算法競賽中對于本題規(guī)模兩者差異不大。但unordered_map的哈希函數(shù)對于整數(shù)類型效率很高通常更快。需要注意的是遍歷unordered_map時鍵值對的順序是不確定的本題不影響結(jié)果。5. 從模板題到實戰(zhàn)算法思想的應(yīng)用與變種5.1 算法思想的核心質(zhì)因數(shù)分解的橋梁作用這道題教會我們的核心思想是許多關(guān)于整數(shù)的全局性質(zhì)問題如約數(shù)個數(shù)、約數(shù)和、歐拉函數(shù)等可以通過質(zhì)因數(shù)分解這座“橋梁”轉(zhuǎn)化為對局部質(zhì)因子指數(shù)的獨立計算問題。分解后問題往往變得簡單且可組合。5.2 實戰(zhàn)變種題舉例AcWing 872. 最大公約數(shù)求多個數(shù)的最大公約數(shù)可以直接使用歐幾里得算法。但理解其質(zhì)因數(shù)分解的視角也很有益最大公約數(shù)就是所有數(shù)公共質(zhì)因子的最低次冪的乘積。LeetCode 319. Bulb Switcher燈泡開關(guān)第i輪切換所有i的倍數(shù)的開關(guān)。最終亮著的燈是其編號約數(shù)個數(shù)為奇數(shù)的燈。根據(jù)我們4.1的結(jié)論這些編號是完全平方數(shù)。所以答案就是sqrt(n)。這道題完美地將約數(shù)個數(shù)奇偶性結(jié)論應(yīng)用于實際場景。判斷一個數(shù)是否只有質(zhì)因子2、3、5丑數(shù)問題可以不斷用2、3、5去除看最后是否剩下1。這本質(zhì)上是特定質(zhì)因數(shù)分解的判定。5.3 性能優(yōu)化進階預(yù)處理質(zhì)數(shù)表當需要頻繁地對多個數(shù)進行質(zhì)因數(shù)分解時每次都從2開始試除會重復(fù)判斷很多合數(shù)。一個優(yōu)化策略是先用線性篩法歐拉篩預(yù)處理出一定范圍內(nèi)比如sqrt(最大值)的所有質(zhì)數(shù)存放在一個數(shù)組中。在分解時只用這些預(yù)處理的質(zhì)數(shù)去試除。 這樣做的好處是試除的次數(shù)等于N的質(zhì)因子個數(shù)加上小于√N的質(zhì)數(shù)個數(shù)比原始的O(√N)常數(shù)更小。當處理批量數(shù)據(jù)時優(yōu)勢明顯。// 線性篩法求質(zhì)數(shù)表 primes[] vectorint get_primes(int n) { vectorint primes; vectorbool st(n 1, false); for (int i 2; i n; i) { if (!st[i]) primes.push_back(i); for (int j 0; primes[j] n / i; j) { st[primes[j] * i] true; if (i % primes[j] 0) break; } } return primes; } // 使用質(zhì)數(shù)表進行質(zhì)因數(shù)分解 unordered_mapint, int factorize(int x, const vectorint primes) { unordered_mapint, int res; for (int p : primes) { if (p x / p) break; // 質(zhì)數(shù)已經(jīng)大于 sqrt(x)退出 if (x % p 0) { while (x % p 0) { x / p; res[p]; } } } if (x 1) res[x]; return res; }掌握約數(shù)個數(shù)的模板其意義遠超解出一道題。它代表了你對數(shù)論基礎(chǔ)工具——質(zhì)因數(shù)分解的熟練運用以及將復(fù)雜問題轉(zhuǎn)化為可計算模型的思維能力。在C實現(xiàn)中注意數(shù)據(jù)類型的選取防止溢出理解循環(huán)邊界條件的寫法并善用STL容器來組織數(shù)據(jù)這些細節(jié)共同決定了代碼的魯棒性和效率。下次遇到約數(shù)相關(guān)的問題不妨先想想能不能先分解質(zhì)因數(shù)