笔记——数论

Bluemoon's Blog / 2024-10-08 / 原文

蓝月の笔记——数论篇

Part 0 约定

令 $\mathcal{P}$ 为质数的集合

所有时间复杂度均指上界

Part 1 质数，$\gcd$

质数就是只有 $1$ 和本身两个因数的数，公因数就是同时使多个数的因数的数，$\gcd$ 就是最大的公因数

质数求法：欧拉筛

在埃氏筛的基础上优化，让每个合数都只被一个质数标记

for (int i = 2; i < kMaxN; i++) {
    if (!vis[i]) {
      pr[++tot] = i;
    }
    for (int j = 1; j <= tot && i * pr[j] < kMaxN; j++) {
      vis[i * pr[j]] = 1;
      if (i % pr[j] == 0) {
        break;     // 如果i是pr[j]的倍数，那么i的倍数也被pr[j]标记过，不用再标记一次
      }
    }
  }

最大公因数可以使用 __gcd() 在 $O(\log n)$ 的时间求出

Part 2 数论分块

考虑以下式子（$n \le 10^{12}$）：

\[\displaystyle\sum_{i=1}^{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$

证明 $$\lfloor\frac{n}{i}\rfloor\le\lfloor\frac{n}{j}\rfloor \Leftrightarrow\lfloor\frac{n}{i}\rfloor\le\frac{n}{j}\Leftrightarrow j\le\frac{n}{\lfloor\frac{n}{i}\rfloor}\Leftrightarrow j\le\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor$$ $$\text{Q.E.D.}$$

那么我们可以 $O(\sqrt{n})$ 枚举答案，$O(1)$ 求出其出现次数，即 $O(\sqrt{n})$ 解决该问题

// BLuemoon_
#include <bits/stdc++.h>

using  namespace std;
using LL = long long;

LL n, ans, l, r;

int main() {
  for (cin >> n, l = 1; l <= n; r = n / (n / l), ans += (r - l + 1) * (n / l), l = r + 1){
  }
  cout << ans << '\n';
  return 0;
}

AT/UVA

Part 3 数论函数

一些定义域是 $\mathbb{N}^{*}$ 的函数

常见数论函数

$\boldsymbol\epsilon(x)=[x=1]$，只有 $x=1$ 是答案为 $1$，否则为 $0$。是狄利克雷卷积中的单位元，后面会解释

$\textbf{id}(x)=x$

$\textbf{1}(x)=1$

$\textbf{d}(x)=\displaystyle\sum_{d|x}1$，即因数个数

$\boldsymbol\sigma(x)=\displaystyle\sum_{d|x}d$，即因数和

$\boldsymbol\varphi(x)=\displaystyle\sum_{i=1}^{x}[\gcd(i,x)=1]$，即小于等于 $x$ 的正整数中与 $x$ 互质的数的个数

令 $x$ 的唯一分解为 $x=\displaystyle\prod_{i=1}^{k}p_i^{c_i}$，其中 $\forall i\in[1,k],p_i\in\mathcal{P},c_i>0$

$\boldsymbol\mu(x)= \begin{cases} 1& x=1\\ 0& \exists i\in[1,k],c_i\ge 2\\ (-1)^{k}& \text{else} \end{cases}$

积性函数

若 $\forall \gcd(i,j)=1,\textbf{f}(i)\textbf{f}(j)=\textbf{f}(ij)$，则称数论函数 $\textbf{f}$ 是积性函数

特别地，若 $\forall i,j\in\mathbb{N^{*}},\textbf{f}(j)=\textbf{f}(ij)$，则称数论函数 $\textbf{f}$ 是完全积性函数

以上 $7$ 个函数都是积性函数

Part 4 狄利克雷卷积

定义两个数论函数 $\textbf{f},\textbf{g}$ 的狄利克雷卷积为 $(\textbf{f}*\textbf{g})(x)=\displaystyle\sum_{d|x}\textbf{f}(d)\textbf{g}(\frac{x}{d})=\displaystyle\sum_{ij=x}\textbf{f}(i)\textbf{g}(j)$，简记为 $\textbf{f}*\textbf{g}$

狄利克雷卷积满足交换律，结合律，对加法的结合律

下面我们证明狄利克雷卷积的单位元是 $\boldsymbol\epsilon$，即对于任何数论函数 $\textbf{f}$ 都有 $\textbf{f}*\boldsymbol\epsilon=\textbf{f}$

\[(\textbf{f}*\boldsymbol\epsilon)(x)=\displaystyle\sum_{d|x}\textbf{f}(d)\boldsymbol\epsilon(\frac{x}{d}) \]
\[\qquad\qquad\quad\,\,\,=\displaystyle\sum_{d|x}\textbf{f}(d)[\frac{x}{d}=1] \]
\[\qquad\qquad\quad\,=\displaystyle\sum_{d|x}\textbf{f}(d)[x=d] \]
\[\quad\!\!=\textbf{f}(x) \]
\[\text{Q.E.D.} \]

Part 5 莫比乌斯反演

考虑证明 $\boldsymbol\mu*\textbf{1}=\boldsymbol\epsilon$：

对于 $x$ 的唯一分解 $x=\displaystyle\prod_{i=1}^{k}p_i^{c_i}$，令 $x^{\prime}=\displaystyle\prod_{i=1}^{k}p_i$
由于有平方质因子时 $\boldsymbol\mu=0$，所以在求和中选了两个相同质因子没有贡献，可以直接扔掉，那么：

\[(\boldsymbol\mu*\textbf{1})(x)=(\boldsymbol\mu*\textbf{1})(x^{\prime}) \]
\[\qquad\quad\quad\!\!=\displaystyle\sum_{d|n^{\prime}}\boldsymbol\mu(d) \]
\[\qquad\qquad\qquad\qquad\quad\qquad\qquad\qquad\qquad\!\!\!\!\!=\displaystyle\sum_{i=0}^{k}\mathrm{C}_{k}^{i}(-1)^{i}1^{k-i}\qquad选出i个质数的方案 \]
\[\qquad\qquad\qquad\qquad\qquad\qquad\quad\,\,\,\!=(-1+1)^{k}\qquad\qquad\quad\!二项式定理 \]
\[\quad=0^k \]
只有在 $k=0$ 即 $n=1$ 时式子才等于 $1$，等价于 $\boldsymbol\epsilon$

\[\text{Q.E.D.} \]

那么莫反结论就容易证明了：当 $\textbf{g}(x)=\displaystyle\sum_{d|x}\textbf{f}(d)$ 时 $\textbf{f}(x)=\displaystyle\sum_{d|n}\boldsymbol\mu(d)\textbf{g}(\frac{x}{d})$

由命题得：$\textbf{g}(x)=(\textbf{f}*\textbf{1})(x)$
两边同时卷一个 $\boldsymbol\mu$，则：$$(\textbf{g}*\boldsymbol\mu)(x)=(\textbf{f}*\boldsymbol\mu*\textbf{1})(x)$$

\[\qquad\quad=(\textbf{f}*\boldsymbol\epsilon)(x) \]
\[\quad=\textbf{f}(x) \]
那么：$$\textbf{f}(x)=(\textbf{g}*\boldsymbol\mu)(x)=\displaystyle\sum_{d|n}\boldsymbol\mu(d)\textbf{g}(\frac{n}{d})$$

\[\text{Q.E.D.} \]

Part 6 杜教筛

杜教筛可以在优于 $O(n)$ 的时间复杂度下解决求数论函数前缀和，即 $\displaystyle\sum_{i=1}^{n}\textbf{f}(i)$，令其等于 $S_n$

我们考虑构造一个数论函数 $\textbf{g}$，尝试证明对于任何 $\textbf{g}$，都有：

\[\displaystyle\sum_{i=1}^{n}(\textbf{f}*\textbf{g})(i)=\displaystyle\sum_{i=1}^{n}\textbf{g}(i)S_{\lfloor\frac{n}{i}\rfloor} \]

将前式的卷积展开，那么其求的本质上是 $\displaystyle\sum_{ij\le n}\textbf{f}(i)\textbf{g}(j)$，枚举 $i,j$ 得到：

\[\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor}\textbf{g}(i)\textbf{f}(j) \]
把第二个和式提取公因式：

\[\displaystyle\sum_{i=1}^{n}\textbf{g}(i)\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor}\textbf{f}(j)=\sum_{i=1}^{n}\textbf{g}(i)S_{\lfloor\frac{n}{i}\rfloor} \]

拆开这个式子：

\[\displaystyle\sum_{i=1}^{n}\textbf{g}(i)S_{\lfloor\frac{n}{i}\rfloor}=\textbf{g}(1)S_n+\sum_{i=2}^{n}\textbf{g}(i)S_{\lfloor\frac{n}{i}\rfloor} \]

即：

\[\textbf{g}(1)S_n=\displaystyle\sum_{i=1}^{n}\textbf{g}(i)S_{\lfloor\frac{n}{i}\rfloor}-\sum_{i=2}^{n}\textbf{g}(i)S_{\lfloor\frac{n}{i}\rfloor}=\displaystyle\sum_{i=1}^{n}(\textbf{f}*\textbf{g})(i)-\sum_{i=2}^{n}\textbf{g}(i)S_{\lfloor\frac{n}{i}\rfloor} \]

那么如果我们可以 $O(1)$ 取出 $\textbf{f}*\textbf{g}$ 和 $\textbf{g}$ 的前缀和，就可以在 $O(n^{\frac{2}{3}})$ 的时间求出答案了。由于作者不会积，复杂度就不证明了

例题：Luogu P4213 【模板】杜教筛

对于 $\textbf{f}=\boldsymbol\mu$，取 $\textbf{g}$ 为 $\textbf{1}$，那么 $\textbf{f}*\textbf{g}=\boldsymbol\epsilon$，证明见 Part 5

那么套用公式，则

\[ans_1=\displaystyle\sum_{i=1}^{n}\boldsymbol\epsilon(i)-\sum_{i=2}^{n}\textbf{1}(i)S_{\lfloor\frac{n}{i}\rfloor}=1-\sum_{i=2}^{n}S_{\lfloor\frac{n}{i}\rfloor} \]

可以用记搜来写，还可以预处理前 $2\times10^6$ 的 $\boldsymbol\mu$，这样就可以通过了

对于 $\textbf{f}=\boldsymbol\varphi$，取 $\textbf{g}=\textbf{1}$，那么 $\textbf{f}*\textbf{g}=\textbf{id}$