#P17602. Cow Function

Cow Function

题目背景

Bessie 和大家正坐在刚刚合并完成的牛棚里,跟着 Farmer John 在一起学习循环展开。

Farmer John 说,如果一个循环展开的步长为 88,会对程序效率有很大的提升。

课后,Farmer John 布置了一道题,要求在 11 秒内算出 f(x)=∑i=1x3ω(i)f(x)=\sum\limits_{i=1}^x3^{\omega(i)}。Bessie 用 2020 分钟打了一个 Θ(nlog⁡2nn)Θ(n\log_2 n\sqrt n) 代码,一交直接 TLE。于是,Bessie 来向你求助。

题目描述

她想要求出对于 k∈{0,1,…,7}k\in\{0,1,\dots,7\},$f(n)=\sum_{i=1}\limits^n[\omega(i)\equiv k\pmod 8]3^{\omega(i)}$ 的值。

上面的算式中,ω(i)\omega(i) 表示 ii 含有几种质因子,例如 ω(12)=ω(6)=2,ω(114514)=3\omega(12)=\omega(6)=2,\omega(114514)=3。

输入格式

仅一行,包含一个整数 nn。

输出格式

共 88 行,分别输出 k=0,1,2,3,4,5,6,7k=0,1,2,3,4,5,6,7 时 $f(n)=\sum_{i=1}\limits^n[\omega(i)\equiv k \pmod 8]3^{\omega(i)}$ 的值。

输入输出样例 #1

输入 #1

30

输出 #1

1
48
108
27
0
0
0
0

输入输出样例 #2

输入 #2

114514

输出 #2

1
32826
344727
1199826
1504818
538731
25515
0

说明/提示

【数据规模与约定】

subtask n≤n\le 所占分值 时间限制
11 100100 1010 500ms500\texttt{ms}
22 2×1062\times10^6 2020 1000ms1000\texttt{ms}
33 3×1073\times10^7
44 10910^9 4000ms4000\texttt{ms}
55 101010^{10} 3030