#P17602. Cow Function
Cow Function
题目背景
Bessie 和大家正坐在刚刚合并完成的牛棚里,跟着 Farmer John 在一起学习循环展开。
Farmer John 说,如果一个循环展开的步长为 ,会对程序效率有很大的提升。
课后,Farmer John 布置了一道题,要求在 秒内算出 。Bessie 用 分钟打了一个 代码,一交直接 TLE。于是,Bessie 来向你求助。
题目描述
她想要求出对于 ,$f(n)=\sum_{i=1}\limits^n[\omega(i)\equiv k\pmod 8]3^{\omega(i)}$ 的值。
上面的算式中, 表示 含有几种质因子,例如 。
输入格式
仅一行,包含一个整数 。
输出格式
共 行,分别输出 时 $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 | 所占分值 | 时间限制 | |
|---|---|---|---|