约数

约数个数

定理：一个数分解质因数为：$p_1^{c_1} \times p_2^{c_2} \times p_3^{c_3} \times … \times p_k^{c_k}$，那么该数的约数个数等于 $(c_1 + 1) \times (c_2 + 1) \times (c_3 + 1) \times … \times (c_k + 1)$

证明：对于该数的约数，一定是 $p_1^{d_1} \times p_2^{d_2} \times p_3^{d_3} \times … \times p_k^{d_k}$, $1 \le d_i \le c_i$，那么对于 $d_i$，共有 $c_i + 1$种方案，再根据乘法原理，共有 $(c_1 + 1) \times (c_2 + 1) \times (c_3 + 1) \times … \times (c_k + 1)$ 个约数

约数之和

定理：一个数分解质因数为：$p_1^{c_1} \times p_2^{c_2} \times p_3^{c_3} \times … \times p_k^{c_k}$，那么该数的约数之和等于 $(p_1^0 + p_1^1 + … + p_1^{c_1}) \times (p_2^0 + p_2^1 + … + p_2^{c_2}) \times … \times (p_k^0 + p_k^1 + … + p_k^{c_k})$

证明：原理与证明约数个数类似