这里是Agakiss的数论学习笔记
#### 数论函数
定义域为$N^{*}$，值域是一个数集的函数
以下数论函数皆用粗体英文字母($\mathbf f、\mathbf g、\mathbf t$)或希腊字母($\mu、\varphi$)表示
#### 基本数论函数
##### 1.欧拉函数：
令$k$为$x$的质因数的个数，则$x=\prod^{k}_{i=1}pi^{ci}$
$$
\varphi(x)=x\ast\prod^{k}_{i=1}(1-\frac{1}{p_i})
$$
##### 2.幺元函数：
$$
\epsilon(x)=[x=1]
$$
##### 3.常函数1(one)：
$$
\mathbf 1(x)=1
$$
$$
\mathbf{one}(x)=1
$$
##### 4.标号函数：
$$
\mathbf{id}(x)=x
$$
##### 5.除数函数：
$$
\sigma_k(x)=\sum_{d|x}d^{k}
$$
$$
\sigma(x,k)=\sum_{d|x}d^{k}
$$
当k=0时，该函数表示x的正因子个数
当k=1时，该函数表示x的正因子之和
#### 运算法则：
##### 函数相加：
$$
(\mathbf f+\mathbf g)(n)=\mathbf f(n)+\mathbf g(n)
$$
##### 数乘：
$$
(x\mathbf f)(n)=x\cdot\mathbf f(n)
$$
#### 狄利克雷卷积
$$
\mathbf t=\mathbf f\ast\mathbf g
$$
$$
\mathbf t(n)=\sum_{i|n}\mathbf f(i)\mathbf g(\frac{n}{i})
$$
$$
\mathbf t(n)=\sum_{ij=n}\mathbf f(i)\mathbf g(j)
$$
狄利克雷卷积的性质：
##### 1.交换律：
$$
\mathbf f\ast\mathbf g=\mathbf g\ast\mathbf f
$$
##### 2.结合律：
$$
(\mathbf f\ast\mathbf g)\ast\mathbf h=\mathbf f\ast(\mathbf g\ast\mathbf h)
$$
##### 3.分配律：
$$
(\mathbf f+\mathbf g)\ast\mathbf h=\mathbf f\ast\mathbf h+\mathbf g\ast\mathbf h
$$
##### 4.与数的结合律：
$$
(x\mathbf f)\ast\mathbf g=x(\mathbf f\ast\mathbf g)
$$
##### 5.单位元：
$$
\epsilon\ast\mathbf f=\mathbf f
$$
##### 6.逆元：
对于每个$\mathbf f(1)\neq0$的函数，都存在一个函数$\mathbf g$使得$\mathbf f\ast\mathbf g=\epsilon$
定义：
$$
\mathbf g(n)=\frac{1}{\mathbf f(1)}\left([n=1]-\sum_{i|n,i\neq1}\mathbf f(i)\mathbf g(\frac{n}{i})\right)
$$
#### 积性函数：
##### 定义：
如果一个数论函数$\mathbf f$满足：当$n\perp m$时有
$$
f(nm)=f(n)f(m)
$$
##### 常见的积性函数：
$$
\epsilon(n)=[n=1].
$$
$$
\mathbf{id}(n)=n.
$$
$$
\mathbf{id}^k(n)=n^k.
$$
$$
\mathbf1(n)=\mathbf{id}^0=1.
$$
$$
\varphi(x)=x\ast\prod^{k}_{i=1}(1-\frac{1}{p_n})
$$
##### 两个重要结论：
$$
两个积性函数的狄利克雷卷积是积性函数
$$
$$
积性函数的逆是积性函数
$$
##### 小技巧：
线筛积性函数不多做讲解，只讲两个有用的推论：
$$
\sigma_0(p^k)=k+1
$$
$$
\varphi(p^k)=p^{k-1}(p-1)
$$
##### 1个推论：
因为$\varphi、\mathbf 1$都是积性函数，所以显然$(\varphi\ast\mathbf 1)$也是积性函数，所以我们只用考虑$p^k$时的取值，于是推导得知：
$$
(\varphi\ast\mathbf 1)(p^k)=p^k
$$
显然我们可以得到：
$$
\mathbf{id}=\varphi\ast\mathbf 1
$$
#### 莫比乌斯反演：
##### 莫比乌斯函数的定义：
$$
\mathbf 1的逆是\mu
$$
##### 求莫比乌斯函数：
再$p^k$的时候：
$$
\mu(p^k)=
\begin{cases}
1&k=0 \\
-1&k=0 \\
0=&k>1
\end{cases}
$$
推广到$n$：
$$
\mu(n)=
\begin{cases}
(-1)^t&n=\prod^{t}_{i=1}{p_t}\\
0&n\neq\prod^{t}_{i=1}{p_t}
\end{cases}
$$
##### 莫比乌斯反演：
根据定义，如果：
$$
\mathbf g=\mathbf f\ast\mathbf 1\Longleftrightarrow\mathbf f=\mathbf f\ast\mathbf1\ast\mu=\mathbf g\ast\mu
$$
将狄利克雷卷积展开，得到：
$$
\mathbf g(n)=\sum_{d|n}f(d)\Longleftrightarrow\mathbf f(n)=\sum_{d|n}\mu(\frac{n}{d})g(d)
$$
##### 另一种证明：
引理：
$$
\mathbf{id}^k的逆是\mathbf t(n)=\mu(n)n^k
$$
设：
$$
\mathbf g(n)=\sum_{d|n}(\frac{n}{d})^k\mathbf f(d)
$$
换个方式表示一下：
$$
\mathbf g(n)=\sum_{d|n}\mathbf{id}^k(\frac{n}{d})\mathbf f(d)
$$
反演一下：
$$
\mathbf f(n)=\sum_{d|n}\mu(\frac{n}{d})(\frac{n}{d})^k\mathbf g(d)
$$
举个栗子：$\varphi=\mu\ast\mathbf{id}$，我们就可以得到：
$$
\varphi(n)=\sum_{d|n}\mu(\frac{n}{d})d
$$
#### 数论分块：
##### 目标：
在已知所有$\sum^{r}_{i=l}f(i)$的情况下，用$O(\sqrt{n})$的复杂度下，求出：
$$
\sum^{n}_{i=1}f(i)\lfloor\frac{n}{i}\rfloor
$$
##### 实现：
引理：
$$
\lfloor\frac{n}{i}\rfloor的取值只有\sqrt{n}种
$$
然后，一个结论：
$$
如果\lfloor\frac{n}{i}\rfloor是一种取值，那么使\lfloor\frac{n}{i}\rfloor=\lfloor\frac{n}{j}\rfloor的j的最大取值为\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor
$$
所以附一下代码（其中$Sum$表示$\sum^{r}_{i=l}f(i)$）：
```cpp
int ans = 0;
for (register int i = 1; i <= n; i = j + 1) {
int j = n / (n / i);
ans += (n / i) * Sum(i, j);
}
```
##### 扩展：
如果在已知所有$\sum^{r}_{i=l}f(i)$的情况下，用$O(\sqrt{n})$的复杂度下，求的是：
$$
\sum^{min(n,m)}_{i=1}f(i)\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor
$$
我们其实只需要稍微改一下，
令每次$j=min(\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor,\lfloor\frac{m}{\lfloor\frac{m}{j}\rfloor}\rfloor)$即可，
再附一下代码（其中$Sum$表示$\sum^{r}_{i=l}f(i)$）：
```cpp
int ans = 0;
for (register int i = 1; i <= min(n, m); i = j + 1) {
int j = min(n / (n / i), m / (m / i));
ans += (n / i) * (m / i) * Sum(i, j);
}
```
#### 数论函数的关系（总结）：
$$
\varphi=\mu\ast\mathbf{id}
$$
$$
\mathbf{id}=\varphi\ast\mathbf1
$$
$$
\epsilon=\mu\ast\mathbf1
$$
#### 杜教筛：
##### 思路1.0：
如果给定函数$\mathbf f,\mathbf g$，令$\mathbf S(n)=\sum^n_{i=1}\mathbf f(i))$，则有：
$$
\sum^{n}_{i=1}(\mathbf f\ast\mathbf g)(i)=\sum^{n}_{i=1}{\sum_{xy=i}{\mathbf f(x)\mathbf g(y)}}=\sum^{n}_{y=1}\mathbf g(y)\sum_{xy\leq n}\mathbf f(x)=\sum^{n}_{y=1}\mathbf g(y)\mathbf S(\lfloor\frac{n}{y}\rfloor)
$$
将第一个和最后一个移项，得：
$$
\mathbf g(1)\mathbf S(n)=\sum^{n}_{i=1}(\mathbf f\ast\mathbf g)(i)-\sum^{n}_{y=2}\mathbf g(y)\ast\mathbf S(\lfloor\frac{n}{y}\rfloor)
$$
看到后半个式子感觉很能数论分块，于是我们有了一个很伪的求$\mathbf S$的方法，
假设$(\mathbf f\ast\mathbf g)(i)$的前缀和与$\mathbf g(i)$的区间和都可以非常快（比如$O(1)$）计算，
那么，我们得到了如下~~伪~~代码：
```cpp
int S(int n) {
int ans = 0;
for (register int i = 1; i <= n; i++)
ans += (f * g)(i);
for (register int i = 2; i <= n; i = j + 1) {
j = n / (n / i);
ans -= Sg(i, j) * S(n / i);
}
ans /= g(1);
return ans;
}
//感性理解一下
```
##### 思路2.0：
现在，我们来继续考虑如何更好的优化它，
引理：
$$
对于任意正整数x,y,z,有\lfloor\frac{\lfloor\frac{z}{x}\rfloor}{y}\rfloor=\lfloor\frac{z}{xy}\rfloor
$$
于是，我们有了新的优化方法，
显然，当我们在某一次计算$\mathbf S(N)$时，必然某一次会计算$\lfloor\frac{N}{x}\rfloor$，那么必然再某一次会计算$\lfloor\frac{\lfloor\frac{N}{x}\rfloor}{y}\rfloor$,那么$\lfloor\frac{N}{xy}\rfloor$,
是不是发现很神奇！
我们如果用记忆化存下$\mathbf S(\lfloor\frac{N}{xy}\rfloor)$的值，
通过数论分块的知识我们可以知道，$\lfloor\frac{N}{i}\rfloor$只有$\sqrt{N}$种取值，
所以求一次$\mathbf S(N)$的，只有$\sqrt{N}$次递归调用，
### 烂尾待更
###### 参考：
###### [1].铃悬的数学小讲堂——狄利克雷卷积与莫比乌斯反演
###### [2].-扶苏-数论进阶-常见数论函数
###### [3].铃悬的数学小讲堂——杜教筛