最近又研究了線性篩素?cái)?shù)方法的擴(kuò)展，的確非常強(qiáng)大。
經(jīng)典的應(yīng)用是線性時(shí)間篩歐拉函數(shù)和求約數(shù)個(gè)數(shù)。我想了一下線性時(shí)間篩約數(shù)和(積性函數(shù))，也是可行的。
對(duì)于一個(gè)大于1的數(shù)n，可以寫成p1 ^ a1 * p2 ^ a2 * ... * pn ^ an，那么n的約數(shù)和就是(p1 ^ 0 + p1 ^ 1 + ... p1 ^ a1) * ... * (pn ^ 0 + ... + pn ^ an)，由此就可以有遞推關(guān)系了：
設(shè)f[i]表示i的約數(shù)和，e[i]表示i的最小素因子個(gè)數(shù)，t[i]表示(p1 ^ 0 + .. + p1 ^ a1)，p1是t的最小素因子，a1是p1的冪次，這樣對(duì)于i * p[j]，如果p[j]不是i的因子，那么根據(jù)積性條件，f[i*p[j]] = f[i] * (1 + p[j])，e[i] = 1，t[i] = 1 + p[j]；如果p[j]是i的因子，那么相當(dāng)于t[i]多了一項(xiàng)p1 ^ (a1 + 1)，首先e[i]++，然后tmp = t[i]，t[i] += p[j] ^ e[i]，f[i*p[j]] = f[i] / tmp * t[i]。這樣也就做到了O(1)的時(shí)間計(jì)算出了f[i*p[j]]同時(shí)也計(jì)算出了附加信息。

這種方法還可以繼續(xù)推廣，例如可以記錄i的最小素因子，這樣就可以做到O(log n)時(shí)間的素因子分解。