poj 3292 Semi-prime H-numbers 筛法

缘起

日常浪费生命 poj 3292 Semi-prime H-numbers

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
形如4n+1(n>=0)这种正整数叫做H数. H素数指的是不能分解为2个或2个以上的H数的大于1的正整数. H半素数指的
是恰能分解为2个H素数的正整数. 给你一个H数h, 求[1,h]中H半素数的个数.

【输入】
多样例. 每行一个H数 h<=1000001, 最后一行是0表示输入结束，不需要处理

【输出】
输出个数. 具体格式见样例

【样例输入】
21 
85
789
0

【样例输出】
21 0
85 5
789 62

【限制】
1s

显然先使用筛法将100w内的 H素数给筛出来(递增). 然后再对每个h，使用[1,h]内的素数计算答案的数量（通过hash防止重复）. 思路是正确的，而且得到的答案也是正确的（和ac程序对拍过）, 可是不幸的是，被T掉了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
//#define LOCAL

int h,p[1000005],num,lim;
bool isp[1000005],book[1000005]; // true表示是H素数

void sieve()
{
	memset(isp, true, sizeof(isp));
	for (int i = 5; i<=1000001; i++)
	{
		if ((i-1)%4)
		{
			isp[i] = false;
			continue;
		}
		if (isp[i])
		{
			p[num++] = i;
			for (int j = (i<<1); j<=1000001; j+=i)
			{
				isp[j] = false;
			}
		}
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	sieve(); // 筛出100w以内的所有H素数
	while(scanf("%d", &h),h)
	{
		int ans = 0;
		memset(book, 0, sizeof(book));
		int lim = (int)(sqrt(1.0*h)+0.5);
		if (lim*lim>h)
		{
			lim--;
		}
		int cnt = upper_bound(p,p+num,min(h/5,lim))-p; // p[0,...,cnt-1]都是<=h的而且<=lim
		int cntt = upper_bound(p,p+num,h/5)-p; // p[0,...,cntt-1]都是<=h/5的
		for (int i = 0; i<cnt; i++)
		{
			for (int j = i; j<cntt&&p[j]<=h/p[i]; j++)
			{
				int ret = p[i]*p[j];
				if (!book[ret])
				{
					book[ret] = true;
					ans++;
				}
			}
		}
		printf("%d %d\n", h, ans);
	}
	return 0;
}

被T掉了

Status Time Limit Exceeded
Length 1132
Lang C++
Submitted 2019-09-01 09:14:56
Shared
RemoteRunId 20822768

那仔细想想——上面为什么慢? 原因是对每个h，都重新计算了一遍，所以更快的做法是筛出100w以内的H素数之后，应该立马再用这些素数筛出100w内的H半素数, 并且递增排序, 然后对于每个h，只需要二分查找就可以得到答案了. 这样才是快的.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
//#define LOCAL

int h,p[1000005],num,pp[1000005],num2;
bool isp[1000005],book[1000005];

void sieve()
{
	memset(isp, true, sizeof(isp));
	for (int i = 5; i<=1000001; i++)
	{
		if ((i-1)%4)
		{
			isp[i] = false;
			continue;
		}
		if (isp[i])
		{
			p[num++] = i;
			for (int j = (i<<1); j<=1000001; j+=i)
			{
				isp[j] = false;
			}
		}
	}
}

void sieve2()
{
	for (int i = 0; i<num; i++)
	{
		for (int j = i; j<num && p[j]<=1000001/p[i]; j++)
		{
			int t = p[i]*p[j];
			if (!book[t])
			{
				pp[num2++] = t;
				book[t] = true;
			}
		}
	}
	sort(pp, pp+num2); // 升序排序, 因为后面要二分查找
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	sieve(); // 筛出100w以内的所有H素数, 并且单调递增
	sieve2(); // 筛出100w内所有的H半素数, 并且单调递增
	while(scanf("%d", &h),h)
	{
		printf("%d %d\n", h, upper_bound(pp, pp+num2, h)-pp); // 直接二分查找,性能飙升
	}
	return 0;
}

ac情况

Status Accepted
Time 32ms
Memory 2828kB
Length 994
Lang C++
Submitted 2019-09-01 09:23:30
Shared
RemoteRunId 20822777