蓝月の笔记——数论篇

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

先证明这个式子：使 $$\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\)

\(\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}\) 是完全积性函数

Part 4 狄利克雷卷积

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