[POJ3292]Semi-prime H-numbers(筛法)

发表于

Semi-prime H-numbers

题目大意

将形如4n+1的数定义为H-Number，其对于乘法的封闭性显然。将可以分解为两个及以上H-Number之积的H-Number定义为H-Composites，否则为H-Prime。H-Composites有一个子集H-Semiprime，指最多只能分解成两个H-Number之积的H-Composites。现在对于每次询问h，希望你能求出小于h的H-Semiprime的个数。

h <= 1e6 + 1

解法

考虑H-Prime和普通质数的相似性，我们可以联想到类似欧拉筛的筛法。将欧拉筛的循环稍作改动之后，我们得到了一个H-Prime筛：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int N = 1e6 + 5;

int flag[N], pri[N], cnt = 0;//flag数组用1标记H-合数；pri是H-质数表，长度为cnt

void sieve () {
	memset(flag, 0, sizeof flag);
	memset(pri, 0, sizeof pri);
	for (int i = 5;i <= N;i += 4) {
		if (!flag[i])
			pri[++cnt] = i;
		for (int j = 1;((j <= cnt) && (i * pri[j] <= N));j++) {
			flag[i * pri[j]] = 1;
			if (i % pri[j] == 0) break;
		}
	}
}

进一步我们发现，在筛选的过程中，每次给 i * pri[j] 打H-Compiosites标记的时候，首先 pri[j] 必定是H-Prime，只需要判断 i 是否是H-Prime即可确定 i * pri[j] 是否是H-Semiprime，所以我们可以一边筛一遍标记H-Semiprime。于是代码就变成了这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int N = 1e6 + 5;

int flag[N], pri[N], cnt = 0;//flag数组用1标记H-合数；pri是H-质数表，长度为cnt
int semi[N], s[N];//semi数组用1标记semiprime；s数组是semi数组的前缀和，用以查询

void sieve () {
	memset(flag, 0, sizeof flag);
	memset(pri, 0, sizeof pri);
	memset(semi, 0, sizeof semi);
	memset(s, 0, sizeof s);
	for (int i = 5;i <= N;i += 4) {
		if (!flag[i])
			pri[++cnt] = i;
		for (int j = 1;((j <= cnt) && (i * pri[j] <= N));j++) {
			flag[i * pri[j]] = 1;
			if (!flag[i]) semi[i * pri[j]] = 1;
			if (i % pri[j] == 0) break;
		}
	}
}`

想强调的一点是，因为我太菜了，所以我一开始把 semi[i * pri[j]] = 1; 写成了 semi[i * pri[j]]++; 。我一开始觉得这两种写法从结果上来说并没有什么区别，但事实上对于比如693这样的数，会因为9 * 77和21 * 33被重复标记。

最后只需要求一下semi数组的前缀和然后O（1）回答每个询问就可以了。完整代码如下：

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 <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdio>
#define pii pair<int, int>
#define makep make_pair
#define pb push_back
#define fi first
#define se second
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int main0 ();
int main () {
	#ifndef ONLINE_JUDGE
		freopen("C:\\Users\\98497\\Desktop\\code\\file.in", "r", stdin);
	#endif
	ios::sync_with_stdio(false);
	main0();
	#ifndef ONLINE_JUDGE
		fclose(stdin);
	#endif
	return 0;
}

const int N = 1e6 + 5;

int flag[N], pri[N], cnt = 0;//flag数组用1标记H-合数；pri是H-质数表，长度为cnt
int semi[N], s[N];//semi数组用1标记semiprime；s数组是semi数组的前缀和，用以查询

void sieve () {
	memset(flag, 0, sizeof flag);
	memset(pri, 0, sizeof pri);
	memset(semi, 0, sizeof semi);
	memset(s, 0, sizeof s);
	for (int i = 5;i <= N;i += 4) {
		if (!flag[i])
			pri[++cnt] = i;
		for (int j = 1;((j <= cnt) && (i * pri[j] <= N));j++) {
			flag[i * pri[j]] = 1;
			if (!flag[i]) semi[i * pri[j]] = 1;
			if (i % pri[j] == 0) break;
		}
	}
}

int main0 () {
	sieve();
	s[0] = 0;
	for (int i = 1;i <= N;i++)
		s[i] = s[i - 1] + semi[i];
	int n;
	while (cin >> n) {
		if (!n) return 0;
		cout << n << ' ' << s[n] << endl;
	}
}