$$\mu * I = \epsilon \\ \phi * I = id \\ id * \mu =\phi$$

日常

• 一个数的约数个数 = $O(n^{1 \over 3})$.
• 整除分块是 $O(n^{0.5})$ 的, 整除分块套整除分块是 $O(n^{0.75})$ 的, 加记忆化就是 $O(n^{2 \over 3})$ 的, 也就是杜教筛.
• 对于一些函数 $gcd(f(a), f(b))=f(gcd(a, b))$, 尤其是一些如此递推的数列: $f(n + 2) = f(n) + f(n + 1)$.
• $fi(n + m) = fi(m)fi(n + 1) + fi(m - 1)fi(n)$.
• 贝叶斯公式:
• 1. $P(A\vert B) = {P(B\vert A)P(A) \over P(B)}$.
  2. $P(A_k\vert B) = {P(B\vert A_k)P(A_k) \over \sum\limits_{i = 1}^n P(B\vert A_i)P(A_i)}$, 其中 $A_{1...n}$ 是完备事件组.
• 树上:
• 1. 直径交于一点.
  2. 两个点集并的直径可以由两个点集自己的直径两段点两两取 $max$ 得到.
  3. 贡献要学会拆.
  4. 一类构成虚树总和的贡献可以使用 $dfs$ 序那套理论 (算其总贡献的 $2$ 倍), 就可以不建出虚树.
  5. 可以用来解方程. (环也可以)
• 一个递推数列可以转化成 $f(x) \over g(x)$. (然后可以求期望之类的)
• 最小生成树有 3 个做法.
• 遇到再说吧.

欧拉的定理 (数论)

$$\phi(n) = \sum\limits_{i \in [1, n]}[\gcd(i, n) = 1]$$

即, $\phi(n)$ 为 $n$ 的缩系大小.

$$\phi(n) = n\prod\limits_{p|n, \text{p is a prime}}{p - 1 \over p}$$

在 $\mod m$, 意义下:

$$a^b \equiv \left\{ \begin{aligned} a^{b \mod \phi(m)}, \gcd(a, m) = 1 \\ a^{\min(b, b \mod \phi(m) + \phi(m))}, \gcd(a, m) \not= 1 \end{aligned} \right.$$

简化一下也是可以的:

$$a^b \equiv a^{\min(a, a \mod \phi(m) + \phi(m))}$$

然后有个结论:

$$\forall x > 1, x^{\phi(m)} \ge m$$

主定理

假设有递推关系式: $T(n) = aT({n \over b}) + f(n), a \ge 1, b > 1$

1. 如果存在常数 $\epsilon > 0$, 有: $f(n) = O(n^{\log_b a - \epsilon})$ (多项式地小于)

   那么, $T(n) = \Theta(n^{\log_b a})$

2. 如果存在常数 $\epsilon > 0$, 有: $f(n) = \Omega(n^{\log_b a + \epsilon})$ (多项式地大于)

   那么, $T(n) = \Theta(f(n))$

3. 如果存在常数 $k \ge 0$, (就是 else) $f(n) = \Theta(n^{\log_b a}\log^k n)$ 那么, $T(n) = \Theta(n^{\log_b a}\log^{k + 1}n)$

不可解决的问题

• 范德蒙德卷积部分和.
• DAG 上每个点可达点个数: 我只会 $O({n^2 \over w})$.