Home AcWing 97 约数之和
Post
Cancel

AcWing 97 约数之和

Link

先给出关于约数的两个结论:

正整数 n 可以分解质因数为 $\prod_{i=1}^k{p_i^{a_i}}=p_1^{a_1}\cdot p_2^{a_2}\cdot\dots\cdot p_k^{a_k}$. 则 n 的正约数个数就是 $f(n)=\prod_{i=1}^k{(a_i+1)}$. 因为 $p_i^{a_i}$ 的正约数为 $p_i^0,p_i^1,\dots,p_i^{a_i}$, 共有 $a_i+1$ 个. 根据排列组合的知识, 显然可以看出 n 的所有正约数之和为 $\prod_{i=1}^k{\sum_{j=0}^{a_i}{p_i^j}}=(p_1^0+p_1^1+\dots+p_1^{a_1})(p_2^0+p_2^1+\dots+p_2^{a_2})\dots(p_k^0+p_k^1+\dots+p_k^{a_k})$.

有了上面这两个结论, 这题应该就很好做了.

This post is licensed under CC BY 4.0 by the author.

AcWing 95 费解的开关

Repeatedly Being Asked to Install Command Line Tools