ZigZagK的博客
[压位+空间优化]Codeforces1017F【The Neutral Zone】题解
2018年8月9日 21:24
查看标签

题目概述

给出 $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;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!