数论学习笔记

这里是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)\)）：

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)\)）：

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)\)）计算，

那么，我们得到了如下伪代码：

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].铃悬的数学小讲堂——杜教筛

数论学习笔记

原文：https://www.cnblogs.com/Agakiss/p/11568755.html