 哈希 平方探查法)
题目大意：给出一个Hash表的大小MSize(<10^4)，以及N个数，用平方探查法（只考虑正增量）依次插入，输出这N个数所在的位置。如果MSize不是素数，则令它等于大于它的最小素数。
主要考察平方探查法。即，插入的元素位置为 (value + index * index) % MSize，index初值为0，如果不能插入，则令index自增，直到 index == MSize，说明无法插入，退出循环。
另外有个坑点是素数的判断中要加入1不是素数这一条，测试点 1即为MSize = 1的情形。
AC代码：
#include <vector> #include <cstdio> #include <cmath> using namespace std; bool isPrime(int n) { if(n == 1) return false; for (int i = 2; i <= sqrt(n); ++i) if(n % i == 0) return false; return true; } int main() { int MSize, N; scanf("%d%d", &MSize, &N); while(!isPrime(MSize)) MSize++; vector<bool> hasNum(MSize, 0); vector<int> position(N, -1); for (int i = 0; i < N; ++i) { int value; scanf("%d", &value); for (int index = 0; index < MSize; ++index) { if(!hasNum[(value + index * index) % MSize]) { hasNum[(value + index * index) % MSize] = true; position[i] = (value + index * index) % MSize; break; } } } for (int i = 0; i < N; ++i) { if(position[i] > -1) printf("%d", position[i]); else printf("-"); if(i < N-1) printf(" "); } return 0; }
