# 「补档计划」数论

### Todo

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

### 扩展欧几里得算法

#### 证明

$ab \neq 0$ 时，设 $ax_1 + by_1 = gcd(a, b)$$bx_2 + (a \text{ mod } b)y_2 = gcd(b, a \text{ mod } b)$

$ax_1 + by_1 = bx_2 + (a \text{ mod } b)y_2 = bx_2 + (a - \lfloor \frac {a} {b} \rfloor \cdot b)y_2 = ay_2 + bx_2 - \lfloor \frac {a} {b} \rfloor \cdot by_2$

### 逆元

#### 费马小定理

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

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

#### 扩展欧几里得

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

$b$ 为素数时有 $gcd(a, b) = 1$，直接求解就好了。

### 中国剩余定理

#### 基本形式

$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 * y + c - b \leq a * x$$c * y + c - b - 1 < a * x$$x > \lfloor \frac {c * y + c - b - 1} {a} \rfloor$故原式$\begin {matrix} = &\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 {matrix}$

$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)$

$S_d(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)$

$a < c$$b < c$ 时，有

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

$M$ 代入，得

$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)$

$a = 0$ 时，即为该算法的边界，此时 $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$

$n = 1$ 时原式为 $1$，因此 $\sum_{d | n} \mu (d) = \left [ n = 1 \right ]$

### 莫比乌斯反演

$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 = g * 1 \Leftrightarrow g = \mu * f$

$f = g * 1$， 则 $f * \mu = g * (1 * \mu) = g * \epsilon = g$
$g = \mu * f$，则 $g * 1 = \mu * f * 1 = \mu * 1 * f = \epsilon * f = f$

#### 变形

$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)$

### 杜教筛

#### 前置技能

##### 一

$x = kab + c$$k, c$ 为非负整数且 $c < ab$，即 $k = \lfloor \frac {x} {ab} \rfloor$
$y = \lfloor \frac x a \rfloor = kb + \lfloor \frac c a \rfloor$，由于 $\lfloor \frac c a \rfloor < b$，所以 $\lfloor \frac y b \rfloor = k$

##### 二

$f, g$ 为两个数论函数，$t$ 为一个完全积性函数，且 $t(1) = 1$，有

$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}

#### 主要形式

$f(n)$ 为一个数论函数，求

$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]$

$f(k)$$\gcd(i, j) = k$ 的个数，$g(k)$$k \ | \ \gcd(i, j)$ 的对数，则

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

$i, j$ 能被 $k$ 整除，那么它们可以写成 $i = k * x_1, j = k * x_2$，的形式，我们只需要求有多少对 $x_1, x_2$ 即可，则

$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$

$T = px$，我们在外层枚举 $T$ 然后对每个质因子计算 $\mu$

$\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')$

$x_1 > 1$ 时，$\mu(p_1 ^ {x_1}) = 0$，则

\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

#### 题解

$\sigma(n)$ 表示 $n$ 的约数和，则第 $i$ 行第 $j$ 列的数为 $\sigma(\gcd(i, j))$，令 $f(k)$$\gcd(i, j) = k$ 的个数，我们考虑分开枚举每一个 $d = \gcd(i, j)$，它对答案的贡献为 $\sigma(d) \times f(d)$，由 「BZOJ 1101」Zap 的式子我们知道

$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$

$g$ 为常函数 $1$，则

\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}