模拟赛考了，就写一下。
本文比较零基础，稍微会点数论的应该都看得懂。
学过的人可以直接跳到后面的部分。
数论函数
数论函数：数论函数指的是定义域是正整数的一类函数。
积性函数
积性函数: 如果一个数论函数 \(f\) 满足 \(f(1)=1\) 且对于任意互质的正整数 \(x,y\) 都有 \(f(xy)=f(x)f(y)\)，则称 \(f\) 是一个积性函数。
完全积性函数: 如果一个数论函数 \(f\) 满足 \(f(1)=1\) 且对于任意正整数 \(x,y\) 都有 \(f(xy)=f(x)f(y)\)，则称 \(f\) 是一个完全积性函数。
不难证明，若正整数 \(x\) 的质因数分解结果为 \(x=\prod p_i^{k_i}\)：
- 若 \(f\) 是积性函数，则 \(f(x)=\prod f(p_i^{k_i})\)。
- 若 \(f\) 是完全积性函数，则 \(f(x)=\prod f(p_i)^{k_i}\)。
下面是一些常见的积性函数（名称可能是我瞎起的）：
- 单位函数：\(\epsilon(n) = [n=1]\) (完全积性)。
- 恒等函数：\(id(n)=n\) (完全积性)。
- 常数函数：\(1(n)=1\) (完全积性)。
- \(d(n)=\sum_{i=1}^n [ i | n ]\)（即 \(n\) 的约数个数）。
- \(\sigma(n)=\sum_{i|n} i\)。
- 欧拉函数：\(\varphi(n)\)，莫比乌斯函数：\(\mu(n)\)。
所有积性函数都可以通过线性筛 \(O(n)\) 求出前 \(n\) 项。
欧拉函数
欧拉函数： \(\varphi(n)=\sum_{i=1}^n [\gcd(i,n)=1]\)。
引理一： \(\sum_{d|n} \varphi(d) = n\)。
证明：设 \(f(x)=\sum_{i=1}^n [\gcd(i,n)=x]\)，显然 \(f(x)=[x|n] \cdot \varphi(\frac{n}{x})\)，所以 \(n=\sum_{i=1}^n f(i)=\sum_{i|n} \varphi(\frac{n}{i})=\sum_{d|n} \varphi(d)\)。
给几个小应用：
- \(\gcd(a,b)=\sum_{d|\gcd(a,b)} \varphi(d)=\sum_{d|a,d|b} \varphi(d)\)。
- \(\sum_{i=1}^n \gcd(i,n)=\sum_{i=1}^n \sum_{d|i,d|n} \varphi(d)=\sum_{d|n} \lfloor \frac{n}{d} \rfloor \cdot \varphi(d)\)。
- \(\sum_{i=1}^n\sum_{j=1}^n \gcd(i,j)=\sum_{d=1}^n \lfloor \frac{n}{d} \rfloor ^2 \cdot \varphi(d)\)，可以用数论分块查询。
莫比乌斯函数
莫比乌斯函数： 记 \(n=\prod_{i=1}^m p_i^{k_i}\)
\[\mu(n)\begin{cases} = 0 & \exists 1\le i\le m，k_i>1 \\ = 1 & n=1 或者 m\equiv 0 \pmod 2 \\ = -1 & m\equiv 1 \pmod 2\\\end{cases}\]
引理二： \(\sum_{d|n} \mu(d)=\epsilon(n)\)。
证明：设 \(n=\prod\limits_{i=1}^m p_i^{k_i},n'=\prod\limits_{i=1}^m p_i\)。
则有 \(\sum_{d|n} \mu(d)=\sum_{d|n'} \mu(d)=\sum\limits_{i=0}^m (-1)^i \cdot \binom{m}{i}=(1-1)^m\)，当且仅当 \(m=0\) 即 \(n=1\) 时结果是 \(1\)，其他情况是 \(0\)。
数论分块
考虑如下式子：
\[\sum_{i=1}^n f(i)g(\lfloor \frac{n}{i} \rfloor)\]
其中 \(f,g\) 是两个数论函数，当我们可以预处理（或者 \(O(1)\) 计算）出 \(f\) 的前缀和时，数论分块可以在 \(O(\sqrt{n})\) 的时间复杂度内求出上式的值。
引理三： \(\lfloor \frac{\lfloor \frac{n}{x} \rfloor}{y}\rfloor = \lfloor \frac{n}{xy} \rfloor\)。
证明：设 \(a=\lfloor \frac{n}{x} \rfloor,\frac{n}{x}=a+b (0\le b1\) 时：</ul>
\[\begin{aligned}g(ab)&=-\sum_{d|ab,d>1} f(d)g(\frac{ab}{d}) \\&=-\sum_{d_1|a,d_2|b,d_1d_2>1} f(d_1)f(d_2)g(\frac{a}{d_1})g(\frac{b}{d_2}) \\&=f(1)f(1)g(a)g(b) - \sum_{d_1|a,d_2|b} f(d_1)f(d_2)g(\frac{a}{d_1})g(\frac{b}{d_2}) \\&=g(a)g(b) - (\sum_{d_1|a} f(d_1)g(\frac{a}{d_1}))(\sum_{d_2|b} f(d_2)g(\frac{b}{d_2})) \\&=g(a)g(b) - (f*g(a))(f*g(b)) \\&=g(a)g(b) - \epsilon(a)\epsilon(b) \\&=g(a)g(b)\end{aligned}\]
例子
- \(\varphi * 1=id\)（由引理一可证）。
- \(\mu * 1 = \epsilon\)，也就是说 \(\mu\) 是 \(1\) 的逆元（由引理二可证）。
- \(1*1=d\)。
- \(id*1=\sigma\)。
- \(id * \mu =\varphi\) （由莫比乌斯反演可证）。
莫比乌斯反演
对于两个数论函数 \(f,g\) 若满足：
\[f(n)=\sum_{d|n} g(d)\]
则有：
\[g(n)=\sum_{d|n} \mu(d)f(\frac{n}{d})\]
写成卷积的形式就是：\(f=g*1 \Leftrightarrow g=f*\mu\)。
证明：\(f=g*1 \Rightarrow f*\mu=g*1*\mu \Rightarrow f*\mu=\epsilon*g=g\)。反过来同理。
由莫比乌斯反演可证例子中的 5.。
当然莫比乌斯反演还有其他两种形式，但是跟主题无关所以这里不进行证明：
- \(f(n)=\sum_{n|d} g(d) \Leftrightarrow g(n)=\sum_{n|d}\mu(\frac{d}{n})f(d)\)。（莫比乌斯变换）。
- 若数论函数 \(t\) 是完全积性函数，且 \(t(1)=1\)，则有：\(f(n)=\sum\limits_{i=1}^n t(i)g(\lfloor \frac{n}{i} \rfloor) \Leftrightarrow g(n)=\sum\limits_{i=1}^n \mu(i)t(i)f(\lfloor \frac{n}{i} \rfloor)\)。（莫比乌斯反演扩展）。
杜教筛
用途：杜教筛可以在亚线性复杂度内求解某些数论函数的前缀和。
注意： 不一定只有积性函数可以用杜教筛求解。
算法
设 \(S(n)=\sum_\limits{i=1}^n f(i)\) 是数论函数 \(f\) 的前缀和。
要算数论函数 \(f\) 的前缀和 \(S(n)\)，我们先去选择另一个数论函数 \(g\)，满足 \(g(1)\ne 0\)，考虑求出 \(f*g\) 的前缀和。
那么：
\[\begin{aligned}\sum_{i=1}^n f*g(i) &=\sum_{i=1}^n \sum_{d|i} g(d)f(\frac{i}{d}) \\&=\sum_{d=1}^n \sum_{x=1}^{\lfloor \frac{n}{d} \rfloor} g(d)f(x) \\&=\sum_{d=1}^n g(d)S(\lfloor \frac{n}{d} \rfloor)\end{aligned}\]
移项，得到：
\[g(1)S(n)=\sum_{i=1}^n f*g(i) - \sum_{d=2}^n g(d)S(\lfloor \frac{n}{d} \rfloor)\]
这就是杜教筛的核心式子。
注意到我们只需要能够快速求出 \(f*g\) 的前缀和和 \(g\) 的前缀和，就可以用数论分块递归地求出 \(S(n)\) 的值了。
下面是大致代码：
[code]int Get(int n){ //求 S(n) int l,r,ans=s_fg(n); //s_fg(n) 是 f*g 的前缀和 for(l=2;lm} O(\sqrt{x}) \\&=\sum_{i=1}^{\lfloor \frac{n}{m} \rfloor} O(\sqrt{\frac{n}{i}}) \\&（省去积分的过程）\\&=O(\frac{n}{\sqrt m})\end{aligned}\]
如果预处理的复杂度是 \(O(m)\)（比如 \(f\) 是积性函数时可以线性筛），那么平衡得最优复杂度是 \(O(n^{\tfrac{2}{3}})\)。
实现
如果使用 unordered_map 或者哈希表存储结果来记忆化，常数会有点大，我们考虑不用哈希表。具体地，我们开一个数组 dp 记录答案，并取一个阈值 \(B\)：
- 如果 \(x\le B\)，就把 \(S(x)\) 存到 dp[x] 中。
- 否则，就把 \(S(x)\) 存到 dp[B+n/x] 中。
接下来我们证明不会出现两个 \(x,y\in R(n)\) 他们用的是 dp 的同一个位置。
证明：\(\le B\) 的情况显然不会出问题，我们只需要证明 \(x,y>B\) 的情况即可。
假设 \(x\ne y\) 但是 \(\lfloor \frac{n}{x} \rfloor=\lfloor \frac{n}{y} \rfloor\)，我们设 \(x=\lfloor \frac{n}{i} \rfloor,y=\lfloor \frac{n}{j} \rfloor\)。
那么有 \(\lfloor \tfrac{n}{\lfloor \tfrac{n}{i} \rfloor} \rfloor=\lfloor \tfrac{n}{\lfloor \tfrac{n}{j} \rfloor} \rfloor\)，根据引理五，这意味着 \(i,j\) 属于同一个块（因为他们所属块的右端点一样），从而必有 \(\lfloor \frac{n}{i} \rfloor = \lfloor \frac{n}{j} \rfloor\)，这与 \(x\ne y\) 矛盾了，所以不会出现这种情况。
所以这样存储是正确的，取 \(B=\lfloor \sqrt{n} \rfloor\) 即可。
应用
(1). 求 \(\mu\) 的前缀和。
取 \(f=\mu,g=1\)，则 \(f*g=\mu*1=\epsilon\)，显然可以快速求出 \(1,\epsilon\) 的前缀和。
(2). 求 \(\varphi\) 的前缀和。
取 \(f=\varphi,g=1\)，则 \(f*g=\varphi*1=id\)，显然可以快速求出 \(1,id\) 的前缀和。
(3). 求 \(\sum_{i=1}^n \varphi(i)\cdot i\)。
取 \(g=id\)，则：
\[\begin{aligned}f*g(n)&=\sum_{d|n} f(d)g(\frac{n}{d}) \\&=\sum_{d|n} \varphi(d)\cdot d\cdot \frac{n}{d} \\&=n\sum_{d|n} \varphi(d) \\&=n^2\end{aligned}\]
所以 \(\sum_{i=1}^n f*g(i)=\frac{n(n+1)(2n+1)}{6}\)。
(4). 求 \(\sum_{i=1}^n \varphi(i)\cdot i^2\)。
取 \(g(n)=n^2\)，同理可得 \(f*g(n)=n^3\)，那么根据数学常识可得 \(\sum_{i=1}^n f*g(i)=(\sum_{i=1}^n i)^2\)。
参考资料
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
