质数篇

核心 ： 线性筛(规定每个合数是由最小质因子得来) 以及二次筛法(区间筛选)

493. 笨小猴

AcWing 726. 质数

AcWing 196. 质数距离

AcWing 197. 阶乘分解

AcWing 4220. 质数路径 bfs+数论

约数篇

核心思想 ：
算术基本定理 :
一整数N可以唯一分解成$N=p_1^{c_1}p_2^{c_2}p_3^{c_3}…p_n^{c_n}$
其中$c_i$ 都是正整数 $p_i$都是质数
N的约数个数为$(c_1+1)(c_2+1)…(c_n+1)$
N的所有正约数的和$(1+p_1+p_1^{2}+…+p_1^{c_1})…(1+p_n+p_n^{2}+…+p_n^{c_2})$

求N的正约数的集合用试除法 $O(N\sqrt{N})$
求1-N每个数的正约数的集合用倍数法 $O(Nlog(N))$

AcWing 869. 试除法求约数

AcWing 870. 约数个数

AcWing 871. 约数之和

AcWing 1291. 轻拍牛头

AcWing 1294. 樱花

AcWing 198. 反素数 dfs+数论

快速幂 也称龟速乘

AcWing 875. 快速幂

AcWing 876. 快速幂求逆元

AcWing 1289. 序列的第k个数

416. 麦森数 经典题型

快速乘

快速乘的模板