2020-2021:teams:legal_string:jxm2001:数论_4

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:数论_4 [2020/09/22 22:29]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:数论_4 [2020/09/23 09:11] (当前版本)
jxm2001 [算法例题]
@@ 行 398: / 行 398: @@
 </code>
 </hidden>
+=== 例题五 ===
+== 题意 ==
+设 $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$，则 $f(n)=\alpha_1+\alpha_2+\cdots \alpha_k$，求
+$$\sum_{i=1}^nf(i!)$$
+== 题解 ==
+发现 $f(ab)=f(a)+f(b)$，于是
+$$\sum_{i=1}^nf(i!)=\sum_{i=1}^n\sum_{j=1}^if(j)=\sum_{i=1}^n(n-i+1)f(i)=(n+1)\sum_{i=1}^nf(i)-\sum_{i=1}^nif(i)$$
+不妨将 $p^k$ 对 $f(n)$ 的贡献分配给 $p,p^2\cdots p^k$，于是
+$$(n+1)\sum_{i=1}^nf(i)-\sum_{i=1}^nif(i)=\sum_{i=1}^{p_i\le n}\sum_{k=1}^{p_i^k\le n}(n+1)\lfloor\frac n{p_i^k}\rfloor-\frac {\lfloor\frac n{p_i^k}\rfloor(\lfloor\frac n{p_i^k}\rfloor+1)}{2}p_i^k$$
+对 $k\ge 2$ 的情况，暴力计算时间复杂度 $O(\sum_{k=2}^{2^k\le n}n^{\frac 1k})\approx O(\sqrt n)$。
+对 $k=1$，则需计算
+$$\sum_{i=1}^{p_i\le n}(n+1)\lfloor\frac n{p_i}\rfloor-\frac {\lfloor\frac n{p_i}\rfloor(\lfloor\frac n{p_i}\rfloor+1)}{2}p_i$$
+通过 $\text{Min_25}$ 筛计算出 $g_1(n)=\sum_{i=1}^n[i\in \text{prime}],g_2(n)=\sum_{i=1}^n[i\in \text{prime}]i$。
+最后考虑整数分块，发现一个块的贡献为 $(g_1(r)-g_1(l-1))(n+1)\lfloor\frac n{p_i}\rfloor-(g_2(r)-g_2(l-1))\frac {\lfloor\frac n{p_i}\rfloor(\lfloor\frac n{p_i}\rfloor+1)}{2}p_i$。
+$g(r)-g(l-1)$ 恰好为 $\text{Min_25}$ 筛的相邻块，可以直接计算。总时间复杂度 $O\left(\frac {n^{\frac 34}}{\log n}\right)$。

2020-2021/teams/legal_string/jxm2001/数论_4.1600784952.txt.gz · 最后更改: 2020/09/22 22:29 由 jxm2001