\[\sum_{p\le n} \frac{1}{p}=O(\log\log n) \]

---

对于 \(n\)，总存在 \(a,b,c\) 使得 \(abc=n\)，且 \(a,b,c\) 要么是质数，要么 \(\le \sqrt{n}\)

---

miller-rabbin 质数：\(2,3,5,7,11,13,82,373\)

---

扩展卢卡斯：

求 \(\binom{n}{m}\mod p\)，\(p\) 较小但不一定为质数
对 \(p\) 质因数分解，完了以后 crt 合并，问题转变为求 \(\binom{n}{m}\bmod p^c\)
变成：

\[\frac{\frac{n!}{p^x}}{\frac{m!}{p^y}\frac{(n-m)!}{p^z}} \cdot p^{y+z-x} \bmod p^c \]

其中每一个分数都和 \(p\) 互质

于是问题变成了求 \(\dfrac{n!}{p^x}\bmod p^c\)，变形成：

\[(p\cdot 2p\cdot\cdots \lfloor\frac{n}{p}\rfloor)\prod_{1\le i\le n,i\not \equiv 0\pmod p}i \]

\[\lfloor\frac{n}{p}\rfloor!\prod_{1\le i\le n,i\not \equiv 0\pmod p}i \]

前一项（\(p\) 的次方都除以 \(p^x\) 的时候除没了）递归处理，后一项拆成若干个长度为 \(p^c\) 的循环，加上最后一个不完整的循环

---