CodeForces 114E Double Happiness (省空间的素数筛法)

r囧r小猫 2022-09-17 11:29 67阅读 0赞

之前学习过一个省空间的素数筛法，见：http://blog.csdn.net/whyorwhnt/article/details/9397289

这回学到一个更省空间的……利用STL标准库中的bitset

以下转自：http://www.cnblogs.com/boloyonghao/archive/2012/07/12/2588599.html

\#include<bister>

using std::bitset;

一句话定义:可自定义位数,用作记录二进制的数据类型.

一,定义和初始化

bitset<n> b; //b有n位,每位都为0;

bitset<n> b(u); //b是unsigned long型u的副本

bitset<n> b(s); //b是string对象s中含有n位字符串的副本

bitset<n> b(s, pos, n); //b是s中从pos位置开始的n个位置的副本

bitset<n> b(s,pos); //b从s的pos位置开始取值到s末尾(注取的值从b的右端开始)

注：①n定义的位数在初始化时按初始值填充,赋值超出的范围舍去,空余的以零填充.

②bitset从string对象读入位集时按从右到左的顺序.

二,操作

b.any(); //查找b是否存在1?

b.none(); //b中不存在1吗?

b.count(); //b中1的个数

b.size(); //b的位数

b\[pos\]; //访问b中pos处的数值

b.test(pos); //检测b中pos处是否为1

b.set(); //把b中所有位 置为1

b.set(pos); //把b中pos位置为1

b.reset(); //把b中所有位置为0

b.reset(pos); //把b中pos位置为0

b.flip(); //b中所有二进制位取反

b.flip(pos); //b中在pos处的二进制位取反

b.to\_ulong; //返回一个同值得unsigned long值

os << b; //把b中位集输出

关于本题：

bool型占一个字节，bitset专门针对位，以位为单位可以将开销降到最小

参考了：http://blog.csdn.net/acdreamers/article/details/12753601

题意：由费马平方和定理我们知道，一个奇素数能表为平方和，那么它一定形如4k+1型的，现在给一个区间\[l,r\]，其中

![20131015184401109][]，求在此区间有多少个4k+1型的素数。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <bitset>
    using namespace std;
    
    const int N = 300000005;
    
    bitset<N> prime;
    
    int main ()
    {
    	int left,right,i;
    	scanf("%d%d",&left,&right);
    	prime.set();  //所有位置置1
    	for (i=3;i*i<=right;i+=2) if (prime[i])
    		for (int j=i*i;j<=right;j+=2*i)
    			prime[j]=false;
    
    	int cnt=(left<=2 && 2<=right);
    	for (i=5;i<=right;i+=4)
    		if (i>=left && prime[i])
    			cnt++;
    	printf("%d\n",cnt);
    	return 0;
    }

[20131015184401109]: /images/20220828/e9fb50bf5de344b097165d55352cdb6f.png

发表评论取消回复

表情：

评论列表（有 0 条评论，67人围观）

还没有评论，来说两句吧...

相关阅读

相关筛法选素数

/ 用筛法求n之前的所有素数 / void 素数(int n){ / 一个数 n 如果是合数，那么它的所有的因子不超过sqrt

青旅半醒/ 2023年07月15日 03:57/ 0 赞/ 92 阅读

相关 POJ 2689【筛法求素数+区间筛素数】

Discription The branch of mathematics called number theory is about properties of numb

桃扇骨/ 2023年07月04日 06:15/ 0 赞/ 130 阅读

相关筛法求素数

include<iostream> include<cstring> using namespace std; const int n=100

本是古典何须时尚/ 2023年03月04日 06:58/ 0 赞/ 102 阅读

相关【素数判断】埃氏筛法和欧拉筛法（线性筛法）

埃氏筛法埃氏筛法的原理是：给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔

本是古典何须时尚/ 2023年01月10日 10:28/ 0 赞/ 240 阅读

相关素数筛法略

用筛法求素数的基本原理，是把从1开始的某一范围内的正整数从小到大顺序排列，逐步筛掉非素数留下素数。用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列

墨蓝/ 2022年10月25日 01:23/ 0 赞/ 277 阅读

相关 CodeForces 114E Double Happiness (省空间的素数筛法)

之前学习过一个省空间的素数筛法，见：http://blog.csdn.net/whyorwhnt/article/details/9397289 这回学到一个更省空间的……利

r囧r小猫/ 2022年09月17日 11:29/ 0 赞/ 68 阅读

相关素数基本（埃氏筛法/线性筛法）

一、检查n是否为素数最简单思路：所有可能的因数全部试一遍。 int gg(int n) { for(int i=2;i<n;i

拼搏现实的明天。/ 2022年05月17日 06:10/ 0 赞/ 392 阅读

相关筛法求素数

用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时

我不是女神ヾ/ 2022年05月12日 14:42/ 0 赞/ 357 阅读

相关素数筛法

//暴力枚举素数筛法 o(n 根号n) for(int i=2;i<=n;i++){ bool g=0; for(int j=2;jj<

╰+哭是因爲堅強的太久メ/ 2022年04月04日 10:54/ 0 赞/ 375 阅读

相关筛法判断素数

1.埃氏筛选法 include <iostream> include <algorithm> using namespace std; con

ゝ一纸荒年。/ 2021年06月22日 15:37/ 0 赞/ 550 阅读