初等數(shù)論學(xué)習(xí)筆記 III：數(shù)論函數(shù)與篩法 _生活百科

初等數(shù)論學(xué)習(xí)筆記 I：同余相關(guān) 。
初等數(shù)論學(xué)習(xí)筆記 II：分解質(zhì)因數(shù) 。

1. 數(shù)論函數(shù)本篇筆記所有內(nèi)容均與數(shù)論函數(shù)相關(guān) 。因此充分了解各種數(shù)論函數(shù)的名稱(chēng) ，定義，符號(hào)和性質(zhì)是必要的。
1.1 相關(guān)定義

數(shù)論函數(shù)：定義域?yàn)檎麛?shù)的函數(shù)稱(chēng)為數(shù)論函數(shù) 。因其在所有正整數(shù)處均有定義，故可視作數(shù)列。OI 中常見(jiàn)的數(shù)論函數(shù)的陪域（即可能的取值范圍）為整數(shù) 。
加性函數(shù)：若對(duì)于任意 \(a, b\in \mathbb{N}_+\) 且 \(a\perp b\) 均有 \(f(ab) = f(a) + f(b)\) ，則稱(chēng) \(f\) 為加性函數(shù) 。注意區(qū)分代數(shù)中的加性函數(shù) 。
積性函數(shù)：若對(duì)于任意 \(a, b\in \mathbb{N}_+\) 且 \(a\perp b\) 均有 \(f(ab) = f(a)f(b)\) ，則稱(chēng) \(f\) 為積性函數(shù) 。易知 \(f(1) = 1\) 是必要條件。
完全積性函數(shù)：若對(duì)于任意 \(a, b\in \mathbb{N}_{+}\) 均有 \(f(ab) = f(a)f(b)\) ，則稱(chēng) \(f\) 為完全積性函數(shù) 。完全積性函數(shù)一定是積性函數(shù) 。
數(shù)論函數(shù)的加法：對(duì)于數(shù)論函數(shù) \(f, g\) ， \(f + g\) 表示 \(f\) 和 \(g\) 對(duì)應(yīng)位置相加，即 \((f + g)(x) = f(x) + g(x)\) 。
數(shù)論函數(shù)的數(shù)乘：對(duì)于數(shù) \(c\) 和數(shù)論函數(shù) \(f\) ， \(c\cdot f\) 表示 \(f\) 的各個(gè)位置乘 \(c\) ，即 \((c\cdot f)(x) = c \cdot f(x)\) 。一般簡(jiǎn)記作 \(cf\) 。
數(shù)論函數(shù)的點(diǎn)乘：對(duì)于數(shù)論函數(shù) \(f, g\) ， \(f \cdot g\) 表示 \(f\) 和 \(g\) 對(duì)應(yīng)位置相乘，即 \((f \cdot g)(x) = f(x)g(x)\) 。為與狄利克雷卷積符號(hào) \(*\) 作區(qū)分，點(diǎn)乘符號(hào)通常不省略。

1.2 常見(jiàn)數(shù)論函數(shù)設(shè) \(n\) 的唯一分解為 \(\prod\limits_{i = 1} ^ m p_i ^ {c_i}\) ，以下是一些常見(jiàn)數(shù)論函數(shù)：

單位函數(shù)：\(\epsilon(n) = [n = 1]\) 。當(dāng) \(n = 1\) 時(shí)取值為 \(1\) ，否則取值為 \(0\) 。它是完全積性函數(shù) 。
常數(shù)函數(shù)：\(1(n) = 1\) 。它是完全積性函數(shù) 。
恒等函數(shù)：\(\mathrm{id}_k(n) = n ^ k\) 。\(\mathrm{id}_1(n)\) 記作 \(\mathrm {id}(n)\) 。它是完全積性函數(shù) 。
除數(shù)函數(shù)：\(\sigma_k(n) = \sum\limits_{d\mid n}d ^ k\) 。\(\sigma_0(n)\) 表示 \(n\) 的約數(shù)個(gè)數(shù) ，記作 \(\tau(n)\) 或 \(d(n)\) 。\(\sigma_1(n)\) 表示 \(n\) 的約數(shù)和，記作 \(\sigma(n)\) 。\(\sigma_k(n)\) 有計(jì)算式 \(\begin{cases} \prod\limits_{i = 1} ^ m (c_i + 1) & k = 0 \\ \sum\limits_{i = 1} ^ m \frac{p_i ^ {(c_i + 1)k} - 1}{p_i - 1} & k > 0\end{cases}\)：根據(jù)乘法分配律， \(n\) 的所有約數(shù)的 \(k\) 次方之和可寫(xiě)作 \(\prod\limits_{i = 1} ^ m\sum\limits_{j = 0} ^ {c_i} p_i ^ {jk}\) ，等比數(shù)列求和后即得。
歐拉函數(shù)：\(\varphi(n) = \sum\limits_{i = 1} ^ n[i\perp n]\) ，表示 \(n\) 以?xún)?nèi)與 \(n\) 互質(zhì)的數(shù)的個(gè)數(shù) 。關(guān)于歐拉函數(shù)的性質(zhì) ，詳見(jiàn)筆記 I.
本質(zhì)不同質(zhì)因子個(gè)數(shù)函數(shù)：\(\omega(n) = \sum\limits_{p \in \mathbb{P}} [p\mid n]\) ，表示 \(n\) 的本質(zhì)不同質(zhì)因子個(gè)數(shù) 。
莫比烏斯函數(shù)：\(\mu(n) = \begin{cases} 1 & n = 1 \\ 0 & \exists d > 1, d ^ 2\mid n \\ (-1) ^ {\omega(n)} & \mathrm{otherwise} \end{cases}\) 。

以上所有函數(shù)除 \(\omega\) 是加性函數(shù)以外，其余均為積性函數(shù) 。根據(jù)計(jì)算式及積性函數(shù)的定義易證。
2. 素?cái)?shù)篩法素?cái)?shù)篩法是數(shù)論體系中最基本的知識(shí)點(diǎn) ，幾乎所有數(shù)論題目都需要篩出 \(1\sim n\) 的所有素?cái)?shù) 。
2.1 埃氏篩素?cái)?shù)埃氏篩用所有已經(jīng)篩出的素?cái)?shù)的倍數(shù)標(biāo)記合數(shù)：從 \(2\) 到 \(n\) 枚舉所有數(shù) \(i\) ，若 \(i\) 未被標(biāo)記，則 \(i\) 是質(zhì)數(shù) ，將 \(i\) 除 \(i\) 以外的倍數(shù)標(biāo)記為合數(shù) 。