ZigZagK的博客
[压位+空间优化]Codeforces1017F【The Neutral Zone】题解
[压位+空间优化]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$ 左右啦。

示例程序

代码还是很短的(呵呵)。

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
#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协议 许可协议。转载请注明出处!
本文写于 2432 天前,最后更新于 2432 天前。
部分信息可能已经过时,博主也可能已经无法对其内容进行解答。
OK