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