题目：https://pintia.cn/problem-sets/994805342720868352/problems/994805389634158592
题意：
给定哈希表的大小和n个数，使用平方探测法解决冲突，为每个数在哈希表中的位置。
如果给定的哈希表的大小不是质数，将其改为最小的比他大的质数。
思路：
比较基础的题目。有两个要注意的点！
1、初始化notprime数组时，需要注意1，也不是质数。特殊处理notprime[1] = true
2、注意考虑prob的边界，应该是哈希表的大小。
因为对于$prob > msize$，设$prob = msize + i$， 则$prob^2 = msize^2 + 2{msize}{i}+i^2$
根据同余$prob^2%msize = i^2%msize$
1 #include<cstdio> 2 #include<cstdlib> 3 #include<map> 4 #include<set> 5 #include<iostream> 6 #include<cstring> 7 #include<algorithm> 8 #include<vector> 9 #include<cmath> 10 #include<stack> 11 #include<queue> 12 13 #define inf 0x7fffffff 14 using namespace std; 15 typedef long long LL; 16 typedef pair<string, string> pr; 17 18 int msize, n; 19 const int maxn = 1e4 + 5; 20 int notprime[maxn * 10]; 21 22 void init() 23 { 24 notprime[1] = true; 25 int now = 2; 26 while(now < 1e5){ 27 if(!notprime[now]){ 28 int tmp = now + now; 29 while(tmp < 1e5){ 30 notprime[tmp] = true; 31 tmp += now; 32 } 33 } 34 now++; 35 } 36 } 37 38 int h[maxn]; 39 int pos[maxn]; 40 41 int main() 42 { 43 init(); 44 scanf("%d%d", &msize, &n); 45 while(notprime[msize]){ 46 msize++; 47 } 48 for(int i = 0; i < n; i++){ 49 int v; 50 scanf("%d", &v); 51 int p = v % msize, prob = 0; 52 while(h[(p + prob * prob) % msize] && prob < msize){ 53 prob++; 54 } 55 if(h[(p + prob * prob) % msize]){ 56 pos[i] = -1; 57 } 58 else{ 59 h[(p + prob * prob) % msize] = v; 60 pos[i] = (p + prob * prob) % msize; 61 } 62 } 63 64 if(pos[0] == -1){ 65 printf("-"); 66 } 67 else{ 68 printf("%d", pos[0]); 69 } 70 for(int i = 1; i < n; i++){ 71 if(pos[i] == -1){ 72 printf(" -"); 73 } 74 else{ 75 printf(" %d", pos[i]); 76 } 77 } 78 printf("\n"); 79 80 return 0; 81 }
原文：https://www.cnblogs.com/wyboooo/p/10656407.html