1078 Hashing (25 分)

Hashing
其中平方探测的k通常小于等于m/2

//1.判断给定的table size是否为素数，不是的话寻找大于该数最小的素数作为替代
//2.平方探测
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int H[maxn]={0};
bool isPrime(int x){
	if(x<=1) return false;
	int sqr = sqrt(x);
	for(int i=2;i<=sqr;i++){
		if(x%i==0) return false;
	}
	return true;
}
int main(){
	int m,n,x;
	cin>>m>>n;
	while(isPrime(m)==false) m++;
	while(n--){
		cin>>x;
		bool flag = false;
		for(int k=0;k<m;k++){
			int now = (x+k*k)%m;
			if(H[now] == 0){
				cout<<now;
				H[now]=1;
				flag=true;
				break;
			}
		}
		if(flag==false) cout<<"-";
		if(n) cout<<" ";
		else cout<<endl;
	}
	return 0;
}