P8104 「LCOI2022」 Cow Function

Bessie 和大家正坐在刚刚合并完成的牛棚里，跟着 Farmer John 在一起学习循环展开。 Farmer John 说，如果一个循环展开的步长为 $8$，会对程序效率有很大的提升。 课后，Farmer John 布置了一道题，要求在 $1$ 秒内算出 $f(x)=\sum\limits_{i=1}^x3^{\omega(i)}$。Bessie 用 $20$ 分钟打了一个 $Θ(n\log_2 n\sqrt n)$ 代码，一交直接 TLE。于是，Bessie 来向你求助。

她想要求出对于 $k\in\{0,1,\dots,7\}$，$f(n)=\sum_{i=1}\limits^n[\omega(i)\equiv k\pmod 8]3^{\omega(i)}$ 的值。 上面的算式中，$\omega(i)$ 表示 $i$ 含有几种质因子，例如 $\omega(12)=\omega(6)=2,\omega(114514)=3$。

无

无

【数据规模与约定】 |subtask|$n\le$|所占分值|时间限制| |:-:|:-:|:-:|:-:| |$1$|$100$|$10$|$500\texttt{ms}$| |$2$|$2\times10^6$|$20$|$1000\texttt{ms}$| |$3$|$3\times10^7$|$20$|$1000\texttt{ms}$| |$4$|$10^9$|$20$|$4000\texttt{ms}$| |$5$|$10^{10}$|$30$|$4000\texttt{ms}$| 如果你需要循环展开生成器，请前往附件下载。