NowCoder猜想(素数筛法+位压缩)
2024-10-18 20:21:16
在期末被各科的大作业碾压快要窒息之际,百忙之中抽空上牛客网逛了逛,无意中发现一道好题,NowCoder猜想,题意很明显,就是个简单的素数筛法,但竟然超内存了,我晕(+﹏+)~ 明明有 3 万多 k 的空间限制……于是我不打表,试了试最暴力的做法,赤裸裸的做法果然超时了,无奈,只好对素数筛法进行位压缩了,这是我目前所能想到的方法了,第一次用上这样的特技,还是调了好一会(位数组里不能用 bool 来定义,具体的话好像 bool 和 int 之类的整型稍有不同;也不能用 int,因其最高位是正负标志位,所以只好用 unsigned int了,同样的原理,用 unsigned char, unsigned short, unsigned long long 等无符号整型都可以),贴个代码先,注释的为纯暴力:
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
const int inf = 0x3fffffff;
const int N = 1e7; class bitarray {
unsigned int sign[];
public:
bitarray() { memset(sign,,sizeof(sign)); }
bool rid(const int &x) const {
return sign[x / ] & ( << (x % ));
}
void wid(const int &x, const int &v) {
sign[x / ] |= (v ? ( << (x % )) : );
}
}; int pri[];
int init_pri(int n = N) {
bitarray bit;
int c = ;
for(int i = ; i <= n; ++i)
if(!bit.rid(i)) {
pri[c++] = i;
for(int j = i << ; j <= n; j += i) bit.wid(j,);
}
return c;
} /*
inline bool isprime(const int &x) {
if(x == 1) return 0;
int m = sqrt(x +0.5);
for(int i = 2; i <= m; ++i)
if(x % i == 0) return 0;
return 1;
} inline int num(const int &n) {
int res = 0;
for(int i = 1; i <= n; i += 2)
if(isprime(i)) ++res;
return n >= 2 ? res + 1 : res;
}
*/ int main() {
int n,num = init_pri();
pri[num++] = inf;
while(~scanf("%d",&n),n) {
int id = lower_bound(pri, pri+num, n) - pri;
if(pri[id] == n) printf("%d\n",id + );
else printf("%d\n",id);
}
return ;
}
提交后发现无论是哪种做法,后台的内存计算都和我自己手算的差很远,不知它是怎么计算的。。。
最新文章
- Java for LeetCode 050 Pow(x, n)
- sell-- wordPOI
- struct和class
- leetcode majority number
- CentOS常用查看系统命令
- unity3d引擎程序员养成
- Memcached总结三:Memcached常用命令及使用说明
- winfrom存储txt日志函数
- JAVA之数组查询binarySearch()方法详解
- 基于.net开发chrome核心浏览器【三】
- IntelliJ IDEA “Finds duplicated code”提示如何关闭
- Python collections模块总结
- Github 开源:使用 .NET WinForm 开发所见即所得的 IDE 开发环境(Sheng.Winform.IDE)【2.源代码简要说明】
- BZOJ 1488: [HNOI2009]图的同构 [Polya]
- java 虚拟机内存模型
- YARN集群的mapreduce测试(五)
- Android 获取外网IP,实测有效
- 安装Linux Mint 17后要做的20件事
- [Visual Studio] 自定义类模板
- 什么是对象:EVERYTHING IS OBJECT(万物皆对象)