\(\textbf{QAQ}\)
令 \(h\) 为两个数论函数 \(f,g\) 的 Dirichlet 卷积 \(f*g\)，则
\[h(n)=\sum_{d|n}f(d)g(\frac{n}{d}) \]它满足结合律，交换律，分配律。
Dirichlet 卷积单位元 \(\epsilon\) 使得 \(\epsilon*f=f\)，它是
\[\epsilon(n)=[n=1] \]两个积性函数 \(f,g\) 的 Dirichlet 卷积 \(h=f*g\) 也是积性函数。
证明，设 \((n,m)=1\)，则
\[\begin{aligned} h(nm)&=\sum_{d|nm}f(d)g(\frac{nm}{d})\\ &=\sum_{d_0|n}\sum_{d_1|n}f(d_0d_1)g(\frac{nm}{d_0d_1})\\ &=\sum_{d_0|n}\sum_{d_1|n}f(d_0)f(d_1)g(\frac{n}{d_0})g(\frac{m}{d_1})\\ &=\bigg(\sum_{d_0|n}f(d_0)g(\frac{n}{d_0})\bigg)\bigg(\sum_{d_1|n}f(d_1)g(\frac{m}{d_1})\bigg)\\ &=h(n)h(m) \end{aligned}\]有积性函数 \(f\)，算术基本定理分解 \(n=\prod_{i=1}^kp_i^{\alpha_i}\)，那么有
\[f(n)=\prod_{i=1}^kf(p_i^{\alpha_i}) \]线性筛积性函数的原理就是它可以用 \(n\) 的最小质因数 \(p_n\) 筛掉 \(n\)，同时我们也可以知道 \(p_n\) 于 \(n\) 中的次数 \(k\)，于是如果我们可以快速计算 \(f\) 在质数幂处 \(f(p^k)\) 的答案，那么我们就可以利用 \((\frac{n}{p_n^k},p^k_n)=1\) 来直接递推出 \(f(n)=f(\frac{n}{p_n^k})f(p_n^k)\)。
比如
\[\varphi(p^k)=p^k-p^{k-1}=(p-1)p^{k-1} \]（ 与 \(p^k\) 不互质的数只有 \(p\) 的倍数 \(p,2p,\dots,p^k-p\)）
其实从这里就能得到
\[\varphi(n)=\prod_{i=1}^k\varphi(p_i^{\alpha_i})=\prod_{i=1}^k(p_i-1)p_i^{\alpha_i-1}=n\prod_{i=1}^k(1-\frac{1}{p_i}) \]