https://www.luogu.com.cn/blog/257146/qian-tan-mo-fan (莫反)
因数个数定理
一个数x分解质因数: \(x = p_1^{a_1} \times p_2^{a_3} \times ... \times p_m^{a_m}\)
则\(x\)的因数个数为 \(\prod_{i = 1}^{m} (a_i + 1)\)
求1~n中每个数的约数个数和
设\(f_x\)表示\(x\)的约数个数，求\(\sum_{x=1}^{n}f_x\)
\(f_x\)可以化简为
\(\sum_{i=1}^{n} [i | x]\)
\(\sum_{i = 1}^{n} \sum_{j=1}^{\frac{n}{i}} [i \times j == x]\)
代入得
\(\sum_{x=1}^{n}f_x\)
\(=\sum_{x=1}^{n} \sum_{i = 1}^{n} \sum_{j=1}^{\frac{n}{i}} [i \times j == x]\)
\(= \sum_{i=1}^{n} \sum_{j=1}^{\frac{n}{i}}\)
\(= \sum_{i=1}^{n} \lfloor \frac{n}{i} \rfloor\)
可以进行整除分块了
标签：约数,frac,杂碎,个数,times,数学,sum From： https://www.cnblogs.com/Facrt/p/16724482.html