占楼# 8.1 数论

---

放在前面：

今天什么 $\sqrt 8$ （

$2h$，从整除草到狄利克雷卷积，再用 $2$ 个小时筛法速通。

所以今天只学到了 $\dfrac{1}{2}$ 左右吧，太抽象了。

---

整除

约数个数大约 $O(n^{\frac{1}{3}})$ 级别，$10^6$ 内最大值为 $240$，$10^18$ 内最大值为 $103680$。（本质不同素因子个数在这两个范围分别为 $7,15$）。

计算约数个数经典 $O(n^{\frac{1}{3}})$解法。

约数个数前缀和计算。

• $O(\sqrt n)$

• $O(n^{\frac{1}{3}}\log n)$

  $$\sigma_k(xy)=\sum\limits_{i|x}\sum\limits_{j|y}[gcd(i,j)=1](\dfrac{xj}{i})^k$$

  素数定理：$\pi(n)\sim \dfrac{n}{\ln n}$。

  哥德巴赫猜想。

---

同余

裴蜀定理，exgcd。

CRT，EXCRT。

多项式环上的中国剩余定理与拉格朗日插值等价，而单位根反演是两者的特殊情况。

$$\left\{\begin{array}{l} x \equiv a_{1}\left(\bmod p_{1}\right) \\ x \equiv a_{2}\left(\bmod p_{2}\right) \\ \quad \vdots \\ x \equiv a_{n}\left(\bmod p_{n}\right) \end{array} \rightarrow x \equiv \sum a_{i} \cdot \frac{P}{p_{i}} \cdot \operatorname{inv}\left(\frac{P}{p_{i}}, p_{i}\right) \quad\left(\bmod P=\prod p_{i}\right)\right.$$

Lucas，Kummer，exLucas。

费马小定理，欧拉定理。

同余最短路。

---

原根

阶。

在已知模数的素数分解的情况下，求阶是 polylog 的。

原根。

有原根当且仅当等于 $1,2,p^k,2p^k$，原根数量为 $\varphi(\varphi(m))$，最小原根不超过 $O(m^{\frac{1}{4}})$。

原根的判定：对于所有 $m$ 的素因子 $p$，检查是否满足 $g^{\frac{\varphi(m)}{p}}\not\equiv1(\bmod m)$。

BSGS。

Index calculus。

---

筛法

筛法

线性筛，埃氏筛。

狄利克雷卷积，狄利克雷前缀和。

卷积性函数：写出贝尔级数，每个素因子上都是线性递推。

数论分块筛：

若 $h=f*g$，则有 $Sh(n)=\sum_if_iSg(\left\lfloor \dfrac{n}{i}\right\rfloor)g(i)$。

杜教筛：

若 $h=f*g$，则有 $Sf(n)g(1)=Sh(n)-\sum_{i\ge 2}Sf(\left\lfloor \dfrac{n}{i}\right\rfloor)$。

常见的贝尔级数：

$$\begin{array}{c} \epsilon(n): 1 \\ I(n): \frac{1}{1-x} \quad \mu(n): 1-x \\ \lambda(n): \frac{1}{1+x} \quad \mu^{2}(n): 1+x \\ 2^{\omega(n)}: \frac{1+x}{1-x} \\ i d_{k}(n): \frac{1}{1-p^{k} x} \quad \sigma_{k}(n): \frac{1}{\left(1-p^{k} x\right)(1-x)} \\ \varphi(n): \frac{1-x}{1-p x} \quad J_{k}(n): \frac{1-x}{1-p^{k} x} \end{array}$$

---

例题集&前头

后面例题更近较慢，因为 $\sqrt8\ \LaTeX$ 太多了，别催。

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---