欧拉函数
定义
又叫做 \(\varphi\) 函数，\(\varphi(x)\) 用来描述不大于 \(x\) 且与 \(x\) 互素的数的个数。
性质
-
满足一切积性函数的性质。
-
若 \(a \bot b\)，则 \(f(a\times b) = f(a) \times f(b)\).
-
能用线性筛或埃氏筛求出。
-
-
\(\text{from}\ 1\ \text{to}\ n\) 中与 \(x\) 互素的数的和为 \(\dfrac{n \times \varphi(x)}{2}\).
-
算数基本定理（唯一分解定理）：\(N = \prod \limits _ {i = 1} ^ {k} p_i ^ {\alpha _ i}\). 其中 \(p_i\) 为素数，\(\alpha _ i\) 为素数 \(p_i\) 的个数，\(k\) 为互不相同的素数的个数。
可以得到欧拉函数的计算公式：\(\varphi(N) = N \times \prod \limits _ {i = 1} ^ {k} \dfrac{p_i - 1}{p_i}\).
证明：设 \(N\) 的其中两个因子 \(p_1,p_2\)，\(\text{from}\ 1\ \text{to}\ n\) 中 \(p_1,p_2\) 的倍数的个数分别是 \(\dfrac{N}{p_1}, \dfrac{N}{p_2}\)，但是有计算重复的，\(p_1 \times p_2\) 的倍数会被计算两次，所以要减去 \(\dfrac{N}{p_1 \times p_2}\). 所以 \(p_1,p_2\) 能为 \(\varphi(N)\) 贡献的答案就是 \(N - \dfrac{N}{p_1} - \dfrac{N}{p_2} + \dfrac{N}{p_1 \times p_2}\). 即 \(N \times (1 - \dfrac{1}{p_1})\times (1 - \dfrac{1}{p_2})\).
根据数学归纳法即可得到上述欧拉函数的计算公式。 -
\(\sum \limits _ {k \mid n} \varphi(k) = n\). 这也是狄利克雷前缀和式。
还有一些其他的性质，感觉用到的很少，就不写了。
莫比乌斯函数
不像是定义的定义
又叫做 \(\mu\) 函数。设 \(N = \prod \limits _ {i = 1} ^ {k} p_i ^ {\alpha _ i}\)，则有：
性质
-
满足一切积性函数的性质。
-
若 \(a \bot b\)，则 \(f(a\times b) = f(a) \times f(b)\).
-
能用线性筛或埃氏筛求出。
-
-
\(\sum \limits _ {k \mid n} \mu(k) = [n = 1]\). 这也是狄利克雷前缀和式。
-
素数的 \(\mu\) 函数的值都是 \(-1\)。（显然）
高维前缀和
显然用求一、二维前缀和的方法是不可以的。
设 \(sum_{i, j}\) 是在第 \(i\) 维，状态集合（不同于状压）为 \(j\) 的前缀和，那么就存在转移方程：
其中，\(state(|j| - 1)\) 表示状态集合大小比 \(j\) 的小 \(1\) 的所有可能状态之一。
某些情况，我们也可以通过改变枚举顺序来滚掉第一维。
狄利克雷前后缀和
它们都是给定一个 \(\{a_n\}\) 来求 \(\{b_n\}\)，只不过是求的式子不同。
狄利克雷前缀和是：\(b_i = \sum \limits _ {j \mid i} ^ n a_j\).
狄利克雷后缀和是：\(b_i = \sum \limits _ {i \mid j} ^ n a_j\).
求后缀和的方法和求前缀和的完全相同，这里只给出求前缀和的方法。
狄利克雷前缀和本质上就是高维前缀和，维度就是筛出来的的素数的个数，状态就是素数的乘积。
设 \(i = \prod \limits ^ {s} p_c ^ {\alpha _ c}\)，\(j = \prod \limits ^ {s} p_c ^ {\beta _ c}\)，且 \(i\) 为 \(j\) 的一个「后继 \(1\)」状态。为了方便理解，我们把质因子出现的次数用行向量表示：\([\alpha_1, \alpha_2, \cdots, \alpha_s], [\beta_1, \beta_2, \cdots, \beta_s]\)，那么一定只存在一个 \(\alpha_k = \beta_k + 1\)，其它的 \(\alpha_{l \ne k} = \beta_{l \ne k}\)。也可以这么理解，对于行向量 \(\alpha\)，我令 \(i \leftarrow i \times p_k\)，那么就有 \(\alpha_k \leftarrow \alpha_k + 1\)。
所以可得狄利克雷前缀和转移方程：
显然可以压掉一维变成：
后缀和也同理。