算是知道quadratic probing是个啥了。。
二次探测：
在要插入的位置a开始
每次加
也就是每次的探测位置是
不是在上一次的基础上+step*step，是在最初地址的基础上加
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long LL;
bool he[N];
bool inhash[N];
int primes[N];
int main(){
he[0]=he[1]=true;
int cnt=0;
for(int i=2;i<=N-1;i++){
if(!he[i])primes[cnt++]= i;
for(int j=0;primes[j]<=(N-1)/i;j++){
he[primes[j]*i]=true;
if(i % primes[j]==0)break;
}
}
int msize,n;
cin>>msize>>n;
//找新的msize
for(int i=msize;i<N-1;i++){
if(!he[i]){
msize=i;
break;
}
}
for(int i=0;i<n;i++){
int x;
cin>>x;
if(i)cout<<" ";
if(!inhash[x%msize]){
inhash[x%msize]=true;
cout<< x%msize;
}
else {
int start=x%msize;
int step;
for( step=1;step<msize;step++){
int pos=(start+step*step)%msize;
if(!inhash[pos]){
inhash[pos]=true;
cout<<pos;
break;
}
}
if(step>=msize){
cout<<"-";
}
}
}
return 0;
}
