题目概述

给出 $f(x)=Ax^3+Bx^2+Cx+D$ ，令 $x=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k},g(x)=a_1f(p_1)+a_2f(p_2)+\cdots +a_kf(p_k)$ 。求 $\sum_{i=1}^{n}g(i)$ 。

解题报告

哇，水题！只需要欧拉筛筛出 $d[i]$ 表示 $i$ 的最小素因子然后就可以 $g(x)=g({x\over d[x]})+f(d[x])$ 啦！

然后你就会看到 $n=3\times10^8,ML=16MB$ 。可以报警了。

存下 $d[i]$ 是不可能的，所以我们换种方法算答案：$\sum_{p}f(p)\sum_{k=1}^{+\infty}\lfloor{n\over p^k}\rfloor$ ，那么只需要找出所有素数（不用存）。

因为 $TL=5s$ ，所以为了缩空间可以(大大)牺牲时间复杂度。由于欧拉筛必须要存下素数，而埃氏筛不用，所以我们考虑用埃氏筛！但就算只开个bool型数组空间还是会跪，怎么办啊？上bitset啦！

然后 $Memory={3\times10^8\times 4\over1024^2\times32}MB\approx38MB$ 。你又可以报警了。

由于 $38$ 和 $16$ 相差不多，我们不需要继续改变解法了，来点黑科技吧！

显然 $2$ 的倍数的状态都是没用的可以直接跳过，我们可以把空间缩到 $19MB$ ，还是会炸……那么我们再把 $3$ 的倍数的状态也跳过，这样空间就变成 $13MB$ 左右啦。

示例程序

代码还是很短的（呵呵）。

#include<cstdio>
#include<bitset>
using namespace std;
typedef unsigned int Uint;
const int maxm=100000000;

int n;Uint A,B,C,D,ans;bitset<maxm+5> vis;

#define ID(x) ((x)-(x)/2-(x)/3+(x)/6)
inline Uint Count(int n,int p) {Uint sum=0;while (n) sum+=(n/=p);return sum;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%u%u%u%u",&n,&A,&B,&C,&D);
    for (int i=2;i<=n;i+=(i&1)+1)
        if ((i==3||i%3)&&!vis[ID(i)]){
            Uint F=A*i*i*i+B*i*i+C*i+D;ans+=F*Count(n,i);
            for (int j=i;j<=n;j+=i)
                if (j%2&&j%3) vis[ID(j)]=true;
        }
    return printf("%u\n",ans),0;
}