間接計數條件
給定正整數 ,每項不超過 ,有多少無序的不同索引配對 滿足 ?數值可以重複;不同索引仍構成一對。逐對測試是直接方法,但因數計數可在許多配對間重用數據。
定義 6.1.1
(Möbius 函數)
Möbius 函數定義在正整數上:;若某個質數平方整除 ,則 ;否則若 是 個不同質數的乘積,則 。
以下結果假設質因數分解唯一。
因數指示式
定理 6.1.2
(Möbius 函數的因數和)
對正整數 ,
因此,對正整數 ,有 。
證明
(因數對應質因數的子集)
若 ,唯一因數是一,而 。否則令其不同質因數為 ,其中 。含平方因數的因數貢獻零;其餘每個因數都是 中若干個不同質數的乘積,因此對應這些質數的一個子集 ,貢獻 。所以其和為
至於推論, 與 的公因數恰好就是 的因數。把恆等式用於 :當 時得 ,否則得 。
證明透視
為何只有 g 等於一時和才是一
唯一不平凡的步驟,是捨去所有含平方因數的因數,並把其餘因數按 的質因數子集編號;這一步用到唯一分解。二項展開 只在 時為零; 時同一式子是空積 ,正好就是 的情況,所以恆等式的兩個情況其實是同一個計算。非無平方因數的因數權重為 是關鍵:若沒有它, 的所有因數之和便不再抵消。
令 為滿足 的索引 個數。
定理 6.1.3
(以 Möbius 和表示互質配對數)
設 ,且所有 ,則
證明
(交換兩個有限和)
對每一對代入因數指示式,再交換求和次序:
右邊所數的集合,是從 個被 整除的索引中選出的不同索引對,所以大小為 。某個 的因數至多為 ,而 時 ,所以求和可在 停止。
二項式係數計算的是索引對,不是不同數值的配對;當 它為零。負項是容斥修正,最終計數非負。
反例模式
質數平方會改變權重
若只按質因數總數給每個因數加正負號,便會出錯。對 ,正確值是 、、。若誤設 ,其和變為 而非 ,錯誤地把最大公因數 當成一。
小例子
例題 6.1.4
(五個數的例子)
對 ,有 、(即 )、(即 )。其餘每個 至多整除一項,所以公式給出
四個索引對對應數值 、、 和 。逐一檢查全部十對可以驗證:其餘六對的最大公因數依次為 。
例題 6.1.5
(相等的數沒有互質配對)
設 。則 、,而 時 。公式給出 ,這是應有的結果:每一對的最大公因數都是 。重複的數值按索引計算,兩項剛好抵消。
計算各項數量
令 為等於 的輸入個數。對每個 ,把 相加求 。Möbius 值也可由因數恆等式得到,不必逐項分解質因數:
mu[1] = 1; mu[2..M] = 0
for d = 1..M:
for multiple = 2d, 3d, ... while multiple <= M:
mu[multiple] -= mu[d]
命題 6.1.6
(此篩法計算 Möbius 值)
外層迴圈到達索引 時,;因此結束時,對所有 都有 。
證明
(對索引作強歸納)
時尚未減去任何值,。設 ,並假設迴圈到達每個 時 。 由 開始,對每個滿足 、 的 (即 的每個真因數 )恰好被減去一次 。因此到達索引 時它等於 。由因數恆等式(取 )有 ,所以這個值等於 。之後的迭代只會改動各自索引之後的項。
兩個倍數迴圈各至多訪問 個位置。計入輸入頻數及最後求和,時間為 ,額外空間為 ,假設整數算術精確且為常數時間。計數可能超出固定寬度整數範圍,實作須選足夠的表示。此界取決於最大值 ,不只取決於輸入數目。
例題 6.1.7
(M 等於 6 的篩法)
從 (索引 )開始。索引 從索引 各減去 :。索引 從索引 和 減去 :。索引 從索引 減去 :。索引 在 以內沒有自身以外的倍數。結果 與定義一致;特別是 和 。
常見錯誤
(以不同數值代替索引計數)
對 ,互質的索引對有兩個,即 和 ,但互質的不同數值配對只有一個。公式給出 ,計算的是索引。先去除重複再計算,回答的是另一個問題。
常見錯誤
(把成本只看成輸入長度的函數)
此篩法配置並掃描長度為 的表。當 而 時,輸入很小,但範圍 使表的大小,以及執行時間和記憶體都很大。
習題與解答
快速檢查
( 是多少?)
先分解 。
解答 · 答案
,因為 整除 。
快速檢查
( 是多少?)
是否無平方因數?
解答 · 答案
,因為 是兩個不同質數的乘積。
快速檢查
(對兩項 ,有多少互質索引對?)
按索引對計算,不按不同數值計算。
解答 · 答案
一對:唯一配對是 ,其最大公因數為一。公式一致:,所以和為 。
快速檢查
(若輸入很少卻含有極大數值,為何所述篩法未必有效率?)
哪個參數決定表的大小?
解答 · 答案
時間及額外記憶體取決於 ; 小本身不代表配置範圍小。
快速檢查
(用公式計算 中的互質索引對數。)
計算 和 ,並檢查 是否成立。
解答 · 答案
、(即 )、、。計數為 。直接檢查:,而 ,所以有兩對。