初等数论

质数相关

质数即一个数的因数只包含 \(1\) 和自己。
筛法请见：质数筛法

模运算相关

首先，存在唯一的整数 \(q,r\) 满足 \(n=qm+r, 0\leqslant r<m\)，\(q\) 就是商，\(r\) 就是余数。
C++ 中模运算可能结果是负数。当 \(n<0\) 时，模运算结果满足 \(-m<r \leqslant 0\)。
因此可以使用

1

(n % m + m) % m

进行取余操作。

求最大公约数

1
2
3
4
5
6
7
8
9
10
11
12
13

#include <iostream>
using namespace std;
int main() {
    int a,b,r;
    cin >> a >> b;
    while (a % b) {
        r = a % b;
        a = b;
        b = r;
    }
    cout << b << endl;
    return 0;
}

同余方程相关

同余方程与二元一次不定方程

数论函数

定义域¹为正整数的函数。

积性函数

积性函数 \(f(n)\) 满足：\(f(1)=1\)，且 \(\forall x,y\in \mathbb{N^*},\gcd(x,y)=1\)，都有 \(f(xy)=f(x)f(y)\)。

完全积性函数 \(f(n)\) 满足：满足：\(f(1)=1\)，且 \(\forall x,y\in \mathbb{N^*}\)，都有 \(f(xy)=f(x)f(y)\)。

性质

若 \(f(x),g(x)\) 为积性函数，则以下函数也为积性函数。

• \(h(x)=f(x^p)\)
• \(h(x)=f^p(x)\)
• \(h(x)=f(x)g(x)\)
• \(h(x)=\sum _{d\mid x} f(d)g(\frac xd)\)（Dirichlet 卷积）

常见积性函数

• \(\varepsilon(n)=[n=1]\)²（完全积性）
• 欧拉函数 \(\varphi(n)=\sum_{i=1}^n[\gcd(i,n)=1]\)

Dirichlet 卷积

有两个数论函数 \(f(x),g(x)\)，其狄利克雷卷积计算的结果 \(h(x)\) 即：

\[ \begin{aligned} h(x) &= \sum _{d\mid x} f(d)g(\frac xd) \newline &= \sum _{ab=x} f(a)g(b) \end{aligned} \]

后一种形式容易理解一点。人话来解释 \(h(x)\) 的计算过程，就是把 \(x\) 的每一对因数 \(a,b\) 找出来（即 \(ab=x\)），然后计算 \(f(a)g(b)\) 和 \(f(b)g(a)\)，再对这对东西求和。

上面的式子可以简记为

\[ h=f*g \]

性质

• 两个积性函数的狄利克雷卷积形式依然是积性函数。

• 满足交换律 结合律 分配律

其他东西

• 单位函数 \(\epsilon(n)=[n=1]\)。
• 对于每个 \(f(1) \neq 0\) 的数论函数 \(f\)，都存在一个函数 \(g\) 使 \(f*g=\epsilon\)（函数逆元）
• 整除分块：对于 \(i,k\in \mathbb{N^*}\)，\(k\) 为定值时，\(\lfloor \frac ki \rfloor\) 有大约 \(\sqrt k\) 种取值。可以用这个做答案关于 \(i\in[x,y], \lfloor \frac ki \rfloor\) 相关的问题（把整除结果相同的数算成一个块来求答案，这样的块大约有 \(\sqrt k\) 个）。
• \(I(n)\) 恒等函数，始终等于 \(1\)。
• \(id(n)=n\) 单位函数。