[Codeforces 114E]Double Happiness

回归的第一道数论题!

(说实话并不简单……)

这个题嘛,主要是这个神奇的数据范围加大了难度。

首先要知道费马平方和定理:一个奇素数是两个正整数的平方和,那么该奇素数必然满足4k+1的形式(k为整数)。注意:2=1+1,所以这个题不要忽略2.

我们发现:17500的平方与3×10^8差不多大,所以可以发现:将17500以内的素数筛出来得到的素数表可以筛出整个范围内的素数。原因很简单,在此不赘述。

也就是说,第一次筛完后第二次筛素数时就按照第一次筛出来的素数去筛。毕竟我们有一张表了,第一次筛素数是“边筛边找”,第二次就直接筛,懒得找。所以比起边筛边找要快得多。

然后就是这个判断:3×10^8太大,bool存不下,怎么办?

只需来一发bitset就可以了,如果没有,就来两发~

 

发表评论