[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;
}
}