# 「补档计划」数论

### Todo

• 快速幂
• gcd
• exgcd
• 逆元
• 中国剩余定理
• 类欧几里德
• Miller-Rabin
• Pollard-Rho
• 数论函数
• 线性筛
• 反演
• BSGS
• 斯特林数
• 原根
• Fast Fourier Transformation
• Fast Number-Theoretic Transform
• 杜教筛
• 洲阁筛

### 逆元

#### 费马小定理

$$a^{p - 1} \equiv \text{ (mod p)}$$

$$a \times a^{p - 2} \equiv \text{ (mod p)}$$

#### 扩展欧几里得

$$ax + by = gcd(a, b)$$

### 中国剩余定理

#### 基本形式

$$x \equiv a_1 \ (\text{mod } m_1)$$
$$x \equiv a_2 \ (\text{mod } m_2)$$
$$\cdots$$
$$x \equiv a_n \ (\text{mod } m_n)$$

### 类欧几里得

1. 若 $a \geq c$，则令 $d = \lfloor \frac {a} {c} \rfloor$，有$$\sum ^ {n}_{x = 0} \lfloor \frac{ax + b}{c} \rfloor = \sum ^ {n}_{x = 0}(\lfloor \frac {(a \% c)x + b}{c}\rfloor + d * x) = d * S_1(n) + \sum_{x = 0} ^ n\lfloor \frac{(a \% c)x + b}{c} \rfloor$$
2. 若 $b \geq c$，则令 $d = \lfloor \frac {b} {c} \rfloor$，有$$\sum ^ {n}_{x = 0} \lfloor \frac{ax + b}{c} \rfloor = \sum ^ {n}_{x = 0}(\lfloor \frac{ax + (b \% c)}{c}\rfloor + d) = d * S_0(n) + \sum ^ {n}_{x = 0} \lfloor \frac{ax + (b \% c)}{c} \rfloor$$
3. 若 $a < c, b < c$ 时，令 $M = \lfloor \frac {an + b} {c} \rfloor$，有$$\sum ^ {n}_{x = 0} \lfloor \frac{ax + b}{c} \rfloor = \sum ^ {n}_{x = 0} \sum ^ {M}_{y = 1}[y \leq \lfloor \frac{ax + b}{c} \rfloor]$$ 即$$\sum ^ {n}_{x = 0} \sum ^ {M - 1}_{y = 0}[y + 1 \leq \lfloor \frac{ax + b}{c} \rfloor]$$ 接下来化简 $y + 1 \leq \lfloor \frac {ax + b} {c} \rfloor$，有$$c \times y + c - b \leq a \times x$$ $$c \times y + c - b - 1 < a \times x$$
$$x > \lfloor \frac {c \times y + c - b - 1} {a} \rfloor$$
故原式\begin {aligned} = &\sum ^ {M - 1}_{y = 0}\sum ^ {n}_{x = 0}[x > \lfloor \frac{c * y + c - b - 1}{a} \rfloor]&\\ = &\sum ^ {M - 1}_{y = 0}(n - \lfloor \frac{c * y + c - b - 1}{a}\rfloor) &\\ = &n * M - \sum ^ {M - 1}_{y = 0} \lfloor \frac{c * y + c - b - 1}{a}\rfloor &\\ \end {aligned}

$$f(a, b, c, n) = \sum_{x = 0} ^ n \lfloor \frac {ax + b} {c} \rfloor$$

$$f(a, b, c, n) = \lfloor \frac {a} {c} \rfloor * S_1(n) + \lfloor \frac {b} {c} \rfloor * S_0(n) + f(a \% c, b \% c, c, n)$$

$$f(a, b, c, n) = \lfloor \frac {a} {c} \rfloor * \frac {n * (n + 1)} {2} + \lfloor \frac {b} {c} \rfloor * (n + 1) + f(a \% c, b \% c, c, n)$$

$$f(a, b, c, n) = n * M - f(c, c - b - 1, a, M - 1)$$

$$f(a, b, c, n) = n * \lfloor \frac {an + b} {c} \rfloor - f(c, c - b - 1, a, \lfloor \frac {an + b} {c} \rfloor - 1)$$

$f(a, b, c, n) = \lfloor \frac {b} {c} \rfloor * (n + 1)$

### 欧拉函数

#### 一些性质

1. $\varphi (1) = 1$。
2. 若 $n$ 是质数 $p$ 的 $k$ 次幂，则 $\varphi (n) = p^k - p^{k - 1} = (p - 1)p^{k - 1}$。
3. 欧拉函数是积性函数，但不是完全积性函数。
4. 当 $n > 1$ 时，$\sum_{i = 1}^{n} i \cdot \left [ gcd(i, n) = 1 \right ] = \frac{n \cdot \varphi(n)} {2}$。
5. 欧拉定理：对于互质的整数 $a, n$，有 $a ^ {\varphi(n)} \equiv 1 \ (\text{mod n})$，那么 $a ^ x \equiv a ^ {x \text{ mod } \varphi(n)} \ (\text{mod n})$。
6. 扩展欧拉定理：对于不互质的整数 $a, n$，$a ^ x \equiv a ^ {x \text{ mod } \varphi(n) + \varphi(n)} \ (\text{mod }n)(x \geq \varphi(n))$。
7. 若 $p \ | \ i$，$p$ 是质数，那么 $\varphi(i * p) = p * \varphi(i)$，否则 $\varphi(p * i) = (p - 1) * \varphi(i)$
8. $\sum_{d | n}\varphi(d) = n$

### 狄利克雷（Dirichlet）卷积

#### 定义

$$(f * g)(n) = \sum_{d | n} f(d) g(\frac{n} {d})$$

#### 一些常见积性函数

1. 除数函数 $\sigma(n)$ 表示 $n$ 的所有正因子之和，即 $\sigma(n) = \sum_{d | n \text{ and } d > 0} d$，$d(n)$ 表示 $n$ 的正因子个数，即 $d(n) = \sum_{d | n}1$。
2. 恒等函数 $id(n) = n$。
3. 单位函数 $\epsilon (n) = \left [ n = 1 \right ]$。
4. 常函数 $1(n) = 1$。

#### 一些性质

1. 交换律：$f * g = g * f$
2. 结合律：$f * g * h = f * (g * h)$
3. 分配率：$f * (g + h) = f * g + f * h$
4. 单位元：$f * \epsilon = \epsilon * f$

#### 常见卷积

1. $d(n) = \sum_{d | n}1 = \sum_{d | n}1(d)1( \frac{n} {d} ) = 1 * 1$
2. $\sigma (n) = \sum_{d | n}d = \sum_{d | n}d(d)1( \frac{n} {d} ) = d * 1$
3. $\varphi (n) = \sum_{d | n} \mu (d) \frac{n} {d} = \sum_{d | n} \mu (d)id( \frac{n} {d}) = \mu * id$
4. $\epsilon (n) = \sum_{d | n} \mu (d) = \sum_{d | n} \mu (d)1( \frac{n} {d}) = \mu * 1$

#### 一些变换

1. 由于 $\varphi = \mu * id$，$\epsilon = \mu * 1$，所以 $1 * \varphi = 1 * \mu * id$，所以 $1 * \varphi = \epsilon * id = id$，即 $\sum_{d | n} \varphi (d) = n$。
2. 由于 $\epsilon = \mu * 1$，$\sum_{d | n} \mu (d) = \left [ n = 1 \right ]$

### 莫比乌斯函数

#### 定义

$$\mu(n) = \left\{\begin{matrix} 1 & n = 1 \\ (-1)^k & n = p_1p_2 \cdots p_k \\ 0 & otherwise \end{matrix}\right.$$

#### 性质

$$\mu(a) \mu(b) = \mu(a \cdot b)$$

$$\sum_{d\mid n}\mu(d) = [n = 1]$$

$$\sum_{d | n} \mu (d) = \sum_{i = 0}^{k}(-1)^i \cdot \binom{k}{i} = (1 - 1)^k = 0$$

### 莫比乌斯反演

$$f(n) = \sum_{d\mid n}g(d)$$

$$g(n) = \sum_{d\mid n}\mu(\frac n d)f(d) = \sum_{d\mid n}\mu(d)f(\frac n d)$$

#### 变形

$$f(x)=\sum_{x|d}g(d) \Leftrightarrow g(x)=\sum_{x|d}\mu(\frac{d}{x})f(d)$$ $$f(i) = \sum_{d = 1}^{\left\lfloor\frac n i\right\rfloor}g(d\cdot i)\Rightarrow g(i) = \sum_{d = 1}^{\left\lfloor\frac n i\right\rfloor}f(d\cdot i)\mu(d)$$

### 杜教筛

#### 前置技能

##### 二

$$f(n) = \sum_{k = 1} ^ {n}t(k)g(\lfloor \frac n k \rfloor) \Leftrightarrow g(n) = \sum_{k = 1} ^ n \mu(k)t(k)f(\lfloor \frac n k \rfloor)$$

\begin{aligned}\sum_{k = 1} ^ n \mu(k)t(k)f(\lfloor \frac n k \rfloor) &= \sum_{k = 1} ^ n\mu(k)t(k)\sum_{i = 1} ^ {\lfloor \frac n k \rfloor}t(i)g(\lfloor \frac {n} {ki} \rfloor) \\ &= \sum_{j = 1} ^ n g(\lfloor \frac n j \rfloor)\sum_{i | j}\mu(i)t(i)t(\frac j i) \\ &= \sum_{j = 1} ^ n g(\lfloor \frac n j \rfloor)t(j)\sum_{i | j}\mu(i) \end{aligned}

\begin{aligned}\sum_{k = 1} ^ n\mu(k)t(k)f(\lfloor n k \rfloor) &= \sum_{j = 1} ^ ng(\lfloor \frac n j \rfloor)t(j)\epsilon(j) \\ &= g(n)g(1) \\ &= g(n) \end{aligned}

#### 主要形式

$$S(n) = \sum_{i = 1} ^ n f(i)$$

$$\sum_{i = 1} ^ n \sum_{d | i}f(d)g(\frac i d) = \sum_{T = 1} ^ ng(T)\sum_{i = 1} ^ {\lfloor \frac n T \rfloor}f(i) = \sum_{i = 1} ^ ng(i)S(\lfloor \frac n i \rfloor)$$

$$g(1)S(n) = \sum_{i = 1} ^ n(f * g)(i) - \sum_{i = 2} ^ ng(i)S(\lfloor \frac n i \rfloor)$$

HDU 3579

### 「BZOJ 1101」Zap

BZOJ 1101

#### 题解

$$\sum_{i = 1} ^ n \sum_{j = 1} ^ m [\gcd(i, j) = k]$$

$$g(k) = \sum_{x = 1} ^ {\lfloor \frac n k \rfloor}f(k \cdot x)$$

$$g(k) = \lfloor \frac n k \rfloor \lfloor \frac m k \rfloor$$

\begin{aligned}f(k) &= \sum_{x = 1}^{\left\lfloor\frac n k\right\rfloor}\mu(x)g(k\cdot x)\\&=\sum_{x = 1}^{\left\lfloor\frac n k\right\rfloor}\mu(x)\left\lfloor\frac n {kx}\right\rfloor\left\lfloor\frac m {kx}\right\rfloor\end{aligned}

$$\lfloor \frac n j \rfloor \geq \lfloor \frac n i \rfloor$$

$$\frac n j \geq \lfloor \frac n i \rfloor$$

$$j \leq \lfloor \frac {n} {\lfloor \frac n i \rfloor} \rfloor$$

### 「BZOJ 2820」YY的GCD

BZOJ 2820

#### 题解

$$\sum_{p}\sum_{i = 1} ^ n\sum_{j = 1} ^ m[\gcd(i, j) = p]$$

$$f(k) = \sum_{i = 1} ^ n\sum_{j = 1} ^ m[\gcd(i, j) = k]$$

$$f(k) = \sum_{x = 1}^{\left\lfloor\frac n k\right\rfloor}\mu(x)\left\lfloor\frac n {kx}\right\rfloor\left\lfloor\frac m {kx}\right\rfloor$$

$$\sum_{p}\sum_{i = 1} ^ n\sum_{j = 1} ^ m[\gcd(i, j) = p] = \sum_p \sum_{x = 1}^{\left\lfloor\frac n p\right\rfloor}\mu(x)\left\lfloor\frac n {px}\right\rfloor\left\lfloor\frac m {px}\right\rfloor$$

$$\sum_{T = 1} ^ n\lfloor \frac n T \rfloor \lfloor \frac m T \rfloor\sum_{k | T}\mu(\frac T k)$$

$$f(T) = \sum\limits_{k \mid T} \mu(\frac{T}{k})$$ $$T = p_1 ^ {x_1} \times p_2 ^ {x_2} \times \cdots \times p_n ^ {x_n}$$ $$T' = p_1 ^ {x_1 - 1} \times p_2 ^ {x_2} \times \cdots \times p_n ^ {x_n}$$

$$f(T') = \sum_{i = 2} ^ k \mu(\frac {T'} {p_i})$$ \begin{aligned}f(T) &= \sum_{i = 1} ^ k \mu(\frac {T} {p_i}) \\ &= \mu(\frac {T} {p_1}) + \sum_{i = 2} ^ k \mu(\frac {T} {p_i}) \\ &= \mu(T') + \sum_{i = 2} ^ k \mu(\frac {T'} {p_i} \times p_1) \\ &= \mu(T') + \sum_{i = 2} ^ k \mu(\frac {T'} {p_i}) \times \mu(p_1) \end{aligned}

$$f(T) = \mu(T') - f(T')$$

\begin{aligned}f(T) &= \sum_{i = 1} ^ k \mu(\frac {T} {p_i}) \\ &= \mu(\frac {T} {p_1}) + \sum_{i = 2} ^ k \mu(\frac {T} {p_i}) \\ &= \mu(T') + \sum_{i = 2} ^ k \mu(\frac {T} {p_i \times p_1 ^ {x_1}} \times p_1 ^ {x_1}) \\ &= \mu(T') + \sum_{i = 2} ^ k \mu(\frac {T} {p_i \times p_1 ^ {x_1}}) \times \mu(p_1 ^ {x_1}) \\ &= \mu(T') \end{aligned}

### 「SDOI 2014」数表

BZOJ 3529

#### 题解

$$f(k) = \sum_{x = 1}^{\left\lfloor\frac n k\right\rfloor}\mu(x)\left\lfloor\frac n {kx}\right\rfloor\left\lfloor\frac m {kx}\right\rfloor$$

$$\sum_{T = 1} ^ n\lfloor \frac n T \rfloor \lfloor \frac m T \rfloor\sum_{k | T}\mu(\frac T k)$$

\begin{aligned}\sum_{i = 1, i \leq a} ^ n\sigma(i)f(i) &= \sum_{i = 1, i \leq a} ^ n\sigma(i)\sum_{T = 1} ^ n\lfloor \frac n T \rfloor \lfloor \frac m T \rfloor\sum_{i | T}\mu(\frac T i) \\ &= \sum_{T = 1} ^ n\lfloor \frac n T \rfloor \lfloor \frac m T \rfloor \sum_{i | T, i \leq a}\sigma(i)\mu(\frac T i)\end{aligned}

### 「51 NOD 1244」莫比乌斯函数之和

51 NOD 1244

#### 题解

$$g(1)S(n) = \sum_{i = 1} ^ n(f * g)(i) - \sum_{i = 2} ^ ng(i)S(\lfloor \frac n i \rfloor)$$

$$\mu * 1 = \epsilon$$

$$S(n) = \sum_{i = 1} ^ n\epsilon(i) - \sum_{i = 2} ^ nS(\lfloor \frac n i \rfloor) = 1 - \sum_{i = 2} ^ nS(\lfloor \frac n i \rfloor)$$

### 「51 NOD 1239」欧拉函数之和

51 NOD 1239

#### 题解

$$g(1)S(n) = \sum_{i = 1} ^ n(f * g)(i) - \sum_{i = 2} ^ ng(i)S(\lfloor \frac n i \rfloor)$$

$$\varphi = \mu * id, \epsilon = \mu * 1$$

$$\varphi * 1 = \epsilon * id = id$$

$$S(n) = \sum_{i = 1} ^ nid(i) - \sum_{i = 2} ^ nS(\lfloor \frac n i \rfloor) = \frac {n \times (n + 1)} {2} - \sum_{i = 2} ^ nS(\lfloor \frac n i \rfloor)$$

BZOJ 3944

### 「HDU 5608」function

HDU 5608

#### 题解

$$\sum_{d | n}f(d) = n ^ 2 - 3n + 2$$

$$\sum_{i = 1} ^ nf(i) \text{ mod }10 ^ 9 + 7$$

$$g(1)S(n) = \sum_{i = 1} ^ n(f * g)(i) - \sum_{i = 2} ^ ng(i)S(\lfloor \frac n i \rfloor)$$

$$f * 1 = \sum_{d | n}f(d) = n ^ 2 - 3n + 2$$

\begin{aligned}S(n) &= \sum_{i = 1} ^ n i ^ 2 - 3i + 2 - \sum_{i = 2} ^ nS(\lfloor \frac n i \rfloor) \\ &= \sum_{i = 1} ^ n i ^ 2 - 3\sum_{i = 1} ^ ni + 2n - \sum_{i = 2} ^ nS(\lfloor \frac n i \rfloor) \\ &= \frac {n * (n + 1) * (2n + 1)} {6} - \frac {3n * (n + 1)} {2} + 2n - \sum_{i = 2} ^ nS(\lfloor \frac n i \rfloor) \\ &= \frac {n * (2n ^ 2 + 3n + 1 - 9n - 9 + 12)} {6} - \sum_{i = 2} ^ nS(\lfloor \frac n i \rfloor) \\ &= \frac {n * (n - 1) * (n - 2)} {3} - \sum_{i = 2} ^ nS(\lfloor \frac n i \rfloor) \end{aligned}

$$h(n) = \sum_{d | n}f(d) = f * 1$$

$$f = \mu * h$$

\begin{aligned}S(n) &= \sum_{i = 1} ^ nf(i) \\ &= \sum_{i = 1} ^ n\sum_{d | i}h(i)\mu(\frac i d) \\ &= \sum_{i = 1} ^ n\sum_{d | i}(i ^ 2 - 3i + 2)\mu(\frac i d) \\ &= \sum_{i = 1} ^ n\sum_{d | i}(i - 1)(i - 2)\mu(\frac i d) \end{aligned}

#