唯一分解定理2

对于任意的正整数$n$都有：
$$n = p_1^{a_1}p_2^{a_2}\cdot\cdot\cdot p_s^{a_s}$$
提出两个问题：

1. $n$有多少个正因子？
2. $n$的所有正因子和是多少？

因子个数

$d(n)$:表示$n$的所有正因子个数。
$$n = p_1^{a_1}p_2^{a_2}\cdot\cdot\cdot p_s^{a_s}$$

对于$n$的任何一个因子(记为:$t$)都整除$n$，而根据唯一分解定理我们可以将$t$也分解。

$$t = p_1^{b_1}p_2^{b_2}\cdot\cdot\cdot p_s^{b_s}$$

此时因为$t$是小于等于$n$的，所以$b_i \leq a_i$。则每一个$b_i$有$a_i+1$种取法。根据乘法原理：
$$d(n) = (a_1+1)\cdot (a_2+1)\cdot\cdot\cdot(a_s+1)$$

因子和

$\phi(n)$:表示$n$的所有正因子之和。
$$n = p_1^{a_1}p_2^{a_2}\cdot\cdot\cdot p_s^{a_s}$$
为了方便：设$n=p_1^{a_1} \cdot p_2^{a_2}$

对于因子：

当$a_1 = 0$，$a_2$可以选择$0, 1, 2, \cdot\cdot\cdot,a_2$

$a_1 = 1$，

…

$a_1 = a_1$

$t = p_1^{a_1} * p_2^{a_2}$

$a_1 = 0$ 因子和有： $p_1^{0} * (p_2^0+p_2^1+…+p_2^{a_2})$

$a_1 = 1$因子和有：$p_1^{1} * (p_2^0+p_2^1+…+p_2^{a_2})$

…

$a_1 = a_1$因子和有：$p_1^{a_1} * (p_2^0+p_2^1+…+p_2^{a_2})$

全部加起来可以得到

$$\phi(n)=(p_1^0 + p_1^1+…+p_1^{a_1})*(p_2^0+p_2^1+…+p_2^{a_2})$$

根据等比数列求和公式

$$\phi(n) = \frac{p_1^{a_1+1} - 1}{1 - p_1} *\frac{p_2^{a_2+1} - 1}{1 - p_2}$$

以此类推当$n = p_1^{a_1}p_2^{a_2}\cdot\cdot\cdot p_s^{a_s}$。

$$\phi(n) = \frac{p_1^{a_1+1} - 1}{1 - p_1}* \cdot\cdot\cdot * \frac{p_s^{a_s+1} - 1}{1 - p_s}$$

推广：

分块

$n \leq 1e9$
$$\sum_{i = 1}^{n} d(i)$$

$$\sum_{i=1}^{n}\phi(i)$$