Codeforces 113C – Double Happiness

神奇结论:可以分解为两个数的平方和的素数满足$n = 4k+1$或者$n=2$。

[2018.8.27 补充] 该结论是费马平方和定理,表述是:奇质数能表示为两个平方数之和的充分必要条件是该素数被4除余1。

那么我们需要找到所有形式为$4k+1$的素数。这题数据范围刁钻,n达到了$3\times 10^8$,时限是3s,由于CF的测评机性能卓越,所以跑一发$O(n)$应该问题不大。

我们需要优化素数筛,维基百科是这样说的:(参考https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)

我们需要用三个优化方法:

  •  第一个就是维基上给出的——当我们发现了一个素数$p$之后,通常我们会从$2p$开始,将所有的$kp$标记为合数,实际上是没有必要的。我们可以直接从$p^2$开始,因为$kp(k \in \{ 1,2,3… p-1\})$一定被小于p的素数筛掉了,那么我们第一层循环中止的条件也可以变成$p^2 \leq n$。
  • 第二就是我们要找的素数是一个奇数,所以只需要考虑奇数。
  • 第三就是我们要找$4k+1$是不是素数,我们一定是在奇数里面找,$p$是素数,$p+2kp$是奇数,所以我们不用考虑$p+(2k-1)p$的数字。

这一题可以说是终极优化+卡常的傻逼题了。实现的时候必须非常谨慎,bool数组开全局是会MLE的,好像必须用bool类型的vector或者bitset==这是玄学??

 

 

说点什么

avatar
50
  Subscribe  
提醒