HDU 5901 Count Primes (模板 + 数论知识)——2016 ACM/ICPC Asia Regional Shenyang Online

传送门

Count primes

Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 635    Accepted Submission(s): 299

Problem Description
Easy question! Calculate how many primes between [1…n]!
 

Input
Each line contain one integer n(1 <= n <= 1e11).Process to end of file.
 

Output
For each case, output the number of primes in interval [1…n]
 

Sample Input
2
3
10
 

Sample Output
1
2
4

题目大意:

1n(n1011) 之间有多少个素数,

解题思路:

板子题目,可以参考 Codeforces 655 F

My Code

/**
2016 - 09 - 19 晚上
Author: ITAK

Motto:

本日的我要超出昨日的我,明日的我要胜过本日的我,
以创作出更好的代码为目标,不断地超出自己。
**/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <time.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const LL INF = 1e9+5;
const LL MAXN = 1e6+5;
const LL MOD = 1e9+7;
const double eps = 1e⑺;
const double PI = acos(-1);
using namespace std;
LL Scan_LL()///输入外挂
{
LL res=0,ch,flag=0;
if((ch=getchar())=='-')
flag=1;
else if(ch>='0'&&ch<='9')
res=ch-'0';
while((ch=getchar())>='0'&&ch<='9')
res=res*10+ch-'0';
return flag?-res:res;
}
void Out(LL a)///输出外挂
{
if(a>9)
Out(a/10);
putchar(a%10+'0');
}

const int N = 5e6 + 2;
bool np[N];
int prime[N], pi[N];
int getprime()
{
int cnt = 0;
np[0] = np[1] = true;
pi[0] = pi[1] = 0;
for(int i = 2; i < N; i++)
{
if(!np[i]) prime[++cnt] = i;
pi[i] = cnt;
for(int j = 1; j <= cnt && i * prime[j] < N; j++)
{
np[i * prime[j]] = true;
if(i % prime[j] == 0) break;
}
}
return cnt;
}
const int M = 7;
const int PM = 2 * 3 * 5 * 7 * 11 * 13 * 17;
int phi[PM + 1][M + 1], sz[M + 1];
void Init()
{
getprime();
sz[0] = 1;
for(int i = 0; i <= PM; i++)
phi[i][0] = i;
for(int i = 1; i <= M; i++)
{
sz[i] = prime[i] * sz[i - 1];
for(int j = 1; j <= PM; j++)
phi[j][i] = phi[j][i - 1] - phi[j / prime[i]][i - 1];
}
}
int sqrt2(LL x)
{
LL r = (LL)sqrt(x - 0.1);
while(r * r <= x) ++r;
return int(r - 1);
}
int sqrt3(LL x)
{
LL r = (LL)cbrt(x - 0.1);
while(r * r * r <= x) ++r;
return int(r - 1);
}
LL get_phi(LL x, int s)
{
if(s == 0) return x;
if(s <= M) return phi[x % sz[s]][s] + (x / sz[s]) * phi[sz[s]][s];
if(x <= prime[s]*prime[s]) return pi[x] - s + 1;
if(x <= prime[s]*prime[s]*prime[s] && x < N)
{
int s2x = pi[sqrt2(x)];
LL ans = pi[x] - (s2x + s - 2) * (s2x - s + 1) / 2;
for(int i = s + 1; i <= s2x; i++) ans += pi[x / prime[i]];
return ans;
}
return get_phi(x, s - 1) - get_phi(x / prime[s], s - 1);
}
LL getpi(LL x)
{
if(x < N) return pi[x];
LL ans = get_phi(x, pi[sqrt3(x)]) + pi[sqrt3(x)] - 1;
for(int i = pi[sqrt3(x)] + 1, ed = pi[sqrt2(x)]; i <= ed; i++)
ans -= getpi(x / prime[i]) - i + 1;
return ans;
}
LL lehmer_pi(LL x)
{
if(x < N) return pi[x];
int a = (int)lehmer_pi(sqrt2(sqrt2(x)));
int b = (int)lehmer_pi(sqrt2(x));
int c = (int)lehmer_pi(sqrt3(x));
LL sum = get_phi(x, a) + (LL)(b + a - 2) * (b - a + 1) / 2;
for (int i = a + 1; i <= b; i++)
{
LL w = x / prime[i];
sum -= lehmer_pi(w);
if (i > c) continue;
LL lim = lehmer_pi(sqrt2(w));
for (int j = i; j <= lim; j++)
sum -= lehmer_pi(w / prime[j]) - (j - 1);
}
return sum;
}
int main()
{
Init();
LL n;
while(~scanf("%I64d",&n))
{
Out(lehmer_pi(n));
puts("");
}
return 0;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » HDU 5901 Count Primes (模板 + 数论知识)——2016 ACM/ICPC Asia Regional Shenyang Online

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡