初等数论

质数相关

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

模运算相关

首先，存在唯一的整数 𝑞,𝑟 满足 𝑛 =𝑞⁢𝑚 +𝑟,0 ⩽𝑟 <𝑚，𝑞 就是商，𝑟 就是余数。
C++ 中模运算可能结果是负数。当 𝑛 <0 时，模运算结果满足 −𝑚 <𝑟 ⩽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;
}

同余方程相关

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

数论函数

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

积性函数

积性函数 𝑓⁡(𝑛) 满足：𝑓⁡(1) =1，且 ∀𝑥,𝑦 ∈ℕ∗,gcd⁡(𝑥,𝑦) =1，都有 𝑓⁡(𝑥⁢𝑦) =𝑓⁡(𝑥)⁢𝑓⁡(𝑦)。

完全积性函数 𝑓⁡(𝑛) 满足：满足：𝑓⁡(1) =1，且 ∀𝑥,𝑦 ∈ℕ∗，都有 𝑓⁡(𝑥⁢𝑦) =𝑓⁡(𝑥)⁢𝑓⁡(𝑦)。

性质

若 𝑓⁡(𝑥),𝑔⁡(𝑥) 为积性函数，则以下函数也为积性函数。

• ℎ⁡(𝑥) =𝑓⁡(𝑥𝑝)
• ℎ⁡(𝑥) =𝑓𝑝⁡(𝑥)
• ℎ⁡(𝑥) =𝑓⁡(𝑥)⁢𝑔⁡(𝑥)
• ℎ⁡(𝑥) =∑𝑑∣𝑥𝑓⁡(𝑑)⁢𝑔⁡(𝑥𝑑)（Dirichlet 卷积）

常见积性函数

• 𝜀⁡(𝑛) =[𝑛 =1]²（完全积性）
• 欧拉函数 𝜑⁡(𝑛) =∑𝑛𝑖=1[gcd⁡(𝑖,𝑛) =1]

Dirichlet 卷积

有两个数论函数 𝑓⁡(𝑥),𝑔⁡(𝑥)，其狄利克雷卷积计算的结果 ℎ⁡(𝑥) 即：

ℎ⁡(𝑥)=∑𝑑∣𝑥𝑓⁡(𝑑)⁢𝑔⁡(𝑥𝑑)=∑𝑎⁢𝑏=𝑥𝑓⁡(𝑎)⁢𝑔⁡(𝑏)

后一种形式容易理解一点。人话来解释 ℎ⁡(𝑥) 的计算过程，就是把 𝑥 的每一对因数 𝑎,𝑏 找出来（即 𝑎⁢𝑏 =𝑥），然后计算 𝑓⁡(𝑎)⁢𝑔⁡(𝑏) 和 𝑓⁡(𝑏)⁢𝑔⁡(𝑎)，再对这对东西求和。

上面的式子可以简记为

ℎ=𝑓∗𝑔

性质

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

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

其他东西

• 单位函数 𝜖⁡(𝑛) =[𝑛 =1]。
• 对于每个 𝑓⁡(1) ≠0 的数论函数 𝑓，都存在一个函数 𝑔 使 𝑓 ∗𝑔 =𝜖（函数逆元）
• 整除分块：对于 𝑖,𝑘 ∈ℕ∗，𝑘 为定值时，⌊𝑘𝑖⌋ 有大约 √𝑘 种取值。可以用这个做答案关于 𝑖 ∈[𝑥,𝑦],⌊𝑘𝑖⌋ 相关的问题（把整除结果相同的数算成一个块来求答案，这样的块大约有 √𝑘 个）。
• 𝐼⁡(𝑛) 恒等函数，始终等于 1。
• 𝑖⁢𝑑⁡(𝑛) =𝑛 单位函数。