P8104 「LCOI2022」 Cow Function

Bessie and the others are sitting in the newly merged barn, studying loop unrolling with Farmer John. Farmer John says that if the unrolling step size is $8$, it can greatly improve program efficiency. After class, Farmer John assigned a problem: compute $f(x)=\sum\limits_{i=1}^x3^{\omega(i)}$ within $1$ second. Bessie wrote a $Θ(n\log_2 n\sqrt n)$ program in $20$ minutes, but it got TLE right after submission. So Bessie came to you for help.

She wants to compute, for $k\in\{0,1,\dots,7\}$, the value of $f(n)=\sum_{i=1}\limits^n[\omega(i)\equiv k\pmod 8]3^{\omega(i)}$. In the formula above, $\omega(i)$ denotes how many distinct prime factors $i$ has. For example, $\omega(12)=\omega(6)=2,\omega(114514)=3$.

A single line containing an integer $n$.

Output $8$ lines. The $k$-th line (for $k=0,1,2,3,4,5,6,7$) should output the value of $f(n)=\sum_{i=1}\limits^n[\omega(i)\equiv k \pmod 8]3^{\omega(i)}$.

Constraints |subtask|$n\le$|points|time limit| |:-:|:-:|:-:|:-:| |$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}$| If you need a loop unrolling generator, please download it from the attachment. Translated by ChatGPT 5