1078 Hashing (25分)(欧拉筛素数打表 + hash平方探测)

1078 Hashing (25分)

The task of this problem is simple: insert a sequence of distinct positive integers into a hash table, and output the positions of the input numbers. The hash function is defined to be $( where$

Note that the table size is better to be prime. If the maximum size given by the user is not prime, you must re-define the table size to be the smallest prime number which is larger than the size given by the user.

Input Specification:

Each input file contains one test case. For each case, the first line contains two positive numbers:

Output Specification:

For each test case, print the corresponding positions (index starts from 0) of the input numbers in one line. All the numbers in a line are separated by a space, and there must be no extra space at the end of the line. In case it is impossible to insert the number, print "-" instead.

Sample Input:

4 4
10 6 4 15

Sample Output:

0 1 4 -



首先讲一下关于哈希表里面平方探测的小知识。


假设哈希函数h(x) = x % prime;
我们知道哈希有很多解决冲突的办法，其中一种就是平方探测。
平方探测就是，用(0, prime)的平方 + x继续进行哈希，直到找到一个不冲突的位置。
为什么是上限是prime - 1呢？
因为如果平放到prime时，(prime * prime + x) % prime == ((prime % prime) * (prime % prime) + x % prime) % prime == x % prime，往下你会发现都是重复的，因此上限是prime - 1。
还有记得....记得prime一定要是一个素数。

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 
 5 const int maxn = 1e5 + 5;
 6 bool vis[maxn];
 7 int prime_list[maxn], cnt;
 8 
 9 void init() {
10     for(int i = 2; i < maxn; i ++) {
11         if(!vis[i]) {
12             prime_list[cnt ++] = i;
13         }
14         for(int j = 0; j < cnt; j ++) {
15             if(i * prime_list[j] > maxn) break;
16             vis[i * prime_list[j]] = true;
17             if(i % prime_list[j] == 0) break;
18         }
19     }
20 }
21 
22 bool _hash[maxn];
23 
24 int main() {
25     init();
26     int n, prime, val;
27     scanf("%d %d", &prime, &n);
28     for(int i = 0; i < maxn; i ++) {
29         if(prime_list[i] >= prime) {
30             prime = prime_list[i];
31             break;
32         }
33     }
34     bool flag;
35     for(int i = 0; i < n; i ++) {
36         scanf("%d", &val);
37         flag = false;
38         for(int j = 0; j < prime; j ++) {
39             if(!_hash[(j * j + val) % prime]) {
40                 _hash[(j * j + val) % prime] = true;
41                 printf("%d%c", (j * j + val) % prime, i == n - 1 ? '
' : ' ');
42                 flag = true;
43                 break;
44             }
45         }
46         if(!flag) printf("-%c", i == n - 1 ? '
' : ' ');
47     }
48     return 0;
49 }