主定理
计算 $T(n)=aT(n/b)+f(n), a \geq 1, b \geq 1$
如果 $\exists \epsilon>0$ 使得 $f(n)=\mathcal{O}(n^{\log_b a - \epsilon})$ ,则 $T(n)=\Theta(n^{\log_b a})$
如果 $f(n)=\Theta(n^{\log_b a})$ ,则 $T(n)=\Theta(n^{\log_b a}\log_2 n)$
如果 $\exists \epsilon>0$使得$f(n)=\Omega(n^{\log_b a + \epsilon})$ ,且 $\exists c<1$ 使得对于充分大的$n$满足$af(n/b) \leq cf(n)$,则$T(n)=\Theta(f(n))$
欧拉定理
$$a^{\phi(n)} \equiv 1 \pmod n,(a,n)=1$$
原根与指标
设 $p$ 是奇质数，$g$ 为 $p$ 的一个原根，若 $g^{p} = q,p \in [0,p-1]$，记 $I(q)=p$ 为指标，则指标满足下列性质 $$I(ab) \equiv I(a)+I(b) \pmod{p-1}$$ $$I(a^k) \equiv kI(a) \pmod{p-1}$$
莫比乌斯反演
$F(n)$ 和 $f(n)$ 是定义在非负整数集合上面的两个函数，并且满足 $F(n) = \sum \limits_ {d \mid n} f(d)$，那么$$\sum \limits_ {d\mid n} \mu(d) F(\frac{n} {d})=f(n)$$
第二类Strling数展开
$${a}^{k}=\sum_ {i=1}^{k} \left\{ i, k \right\} * \binom {i} {a} \times i!$$