前言
在虎撲和各種論壇上經(jīng)常有小學(xué)奧數(shù)題出現(xiàn)箩艺。每次遇到這樣的題都會(huì)被蜜罐——自己總抱有一種“前事不忘后事之師”的“敝帚自珍”鹃锈、收破爛的心態(tài)荤胁，總是不肯承認(rèn)自己不再擅長小時(shí)候那些初等數(shù)學(xué)中比較復(fù)雜的問題。有時(shí)候屎债，看到諸如“求陰影面積”的題還是會(huì)去做輔助線建系用初等方法費(fèi)勁吧啦地求解仅政，解出后卻有種悵然若失垢油、捶胸頓足之感——又被網(wǎng)絡(luò)上的“時(shí)間小偷”給盤了！
今天又看到一個(gè)這種問題圆丹，浪費(fèi)了將近一個(gè)半小時(shí)才徹底搞明白前因后果滩愁。真是后悔啊……
起手
projecteuler 108
projecteuler 110
史上最賤的數(shù)學(xué)題
丟番圖倒數(shù)、丟番圖方程是一個(gè)很經(jīng)典的問題辫封。但其變種卻引申出了數(shù)學(xué)中許多非常深刻的理論硝枉。這道題化簡后得到是一個(gè)二次的問題：
- 求解
對(duì)于不同 n 時(shí)，
解的個(gè)數(shù)倦微。
由于 x妻味、y、n 分別都是正整數(shù)欣福，且題目存在隱含條件 弧可。因此，問題便簡化為求解一個(gè)形如
的整數(shù)有多少個(gè)因數(shù)了劣欢。
編程 1
上面的問題很簡單棕诵，也比較直觀。
- 對(duì)于任意正整數(shù) n凿将，可以通過短除法求出其質(zhì)因數(shù)分解校套。如果預(yù)先有質(zhì)數(shù)表（篩法）的話效率更高。沒有質(zhì)數(shù)表對(duì)于較小的分解也問題不大牧抵。
def prime_factors(n: int):
results = []
while n % 2 == 0:
results.append(2)
n = n // 2
for i in range(3, int(math.sqrt(n)) + 1, 2):
while n % i == 0:
results.append(i)
n = n // i
if n > 2:
results.append(n)
return results
- 如想得到所有因子笛匙，可以算出因子個(gè)數(shù)后循環(huán)生成得到。
因此犀变，對(duì)于給定任意 n妹孙，求其有多少個(gè)因子/多少組 解的問題，求解非常簡單获枝。
然而蠢正，這個(gè)問題絕非上述分析那么簡單。難點(diǎn)在于如何滿足“恰好”這個(gè)條件省店。
分析
因子的數(shù)量
相對(duì)于 projecteuler 110 求解 4M 個(gè)解時(shí)對(duì)應(yīng)的 n 的大小嚣崭，本題有異曲同工之妙，但難度稍低懦傍。目前雹舀，我們能夠得到任何可以計(jì)算的正整數(shù) n 對(duì)應(yīng)的解的個(gè)數(shù)，那如何找到特定解的個(gè)數(shù)對(duì)應(yīng)的最小的 n 值呢粗俱？
繼續(xù)分析说榆。首先，比較好理解的一點(diǎn)：解的個(gè)數(shù)是 因子個(gè)數(shù)加一除以二。因?yàn)?n 本身是
的因子签财，但只計(jì)入一次稍味；而其他解則為因子的對(duì)稱配對(duì)，又由于
荠卷，故可以通過因子個(gè)數(shù)得到解的個(gè)數(shù)模庐，反之亦然。
因此油宜，對(duì)于解的個(gè)數(shù)分別為 100掂碱、1000、1000000 (1M)的三個(gè)問題慎冤，我們需要得到的因子個(gè)數(shù)則為 199疼燥、1999、1999999 (2M-1)蚁堤。通過 O(1) 素?cái)?shù)查表得知醉者，199、1999 為素?cái)?shù)披诗，而 1999999 非素?cái)?shù)撬即。通過質(zhì)因數(shù)分解函數(shù)求得 1999999 = 17 × 71 × 1657。此時(shí)呈队，所需條件都已求得
滿足條件
為了滿足解個(gè)數(shù)為“恰好”的條件剥槐，n 因數(shù)分解后的因子個(gè)數(shù)必須滿足上述條件。同時(shí)宪摧，為了滿足“最小”的條件粒竖，計(jì)算出的 n 一定是按照因數(shù)分解后，質(zhì)因數(shù)冪次從大到小排列的結(jié)果—— 對(duì)正整數(shù)成立几于。
總結(jié)
為什么解題遇到了困難：
- 最初并沒有把這個(gè)問題分析清楚蕊苗。在得到約分后的式子后，便盲目使用暴力法求解沿彭。后序優(yōu)化也在考慮分治法朽砰，而非從根本上分析問題的本質(zhì)。
- 沒有想清楚質(zhì)因數(shù)和解的個(gè)數(shù)之間的關(guān)系膝蜈。
- 分解質(zhì)因數(shù)時(shí)算法效率過低锅移，即便沒有素?cái)?shù)表熔掺、不用篩法饱搏，也應(yīng)該盡可能避開無效的循環(huán)次數(shù)，而非從頭到尾走一遍置逻。
- 對(duì)于算法的重用推沸。算法的關(guān)鍵在于質(zhì)因數(shù)分解算法，但問題的關(guān)鍵在于如何解構(gòu)、分析背后的本質(zhì)鬓催。分析清楚之后肺素，只需要一個(gè)算法和一些輔助語句即可得到答案。
