【PAT甲级】1078 Hashing (25 分)(哈希表二次探测法)

时间:2022-06-23 15:20:02

题意:

输入两个正整数M和N(M<=10000,N<=M)表示哈希表的最大长度和插入的元素个数。如果M不是一个素数,把它变成大于M的最小素数,接着输入N个元素,输出它们在哈希表中的位置(从0开始),如有冲突采取二次探测法处理冲突。

trick:

测试点1包含M为1的数据,1不是素数。。。

AAAAAccepted code:

 #include<bits/stdc++.h>
using namespace std;
int a[];
int ans[];
int vis[];
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int m,n;
cin>>m>>n;
int flag=;
for(int i=;i*i<=m;++i)
if(m%i==){
flag=;
break;
}
if(flag||m==)
for(int i=m+;;++i){
int flag2=;
for(int j=;j*j<=i;++j)
if(i%j==){
flag2=;
break;
}
if(!flag2){
m=i;
break;
}
}
for(int i=;i<=n;++i)
cin>>a[i];
for(int i=;i<=n;++i){
int tamp=a[i]%m;
if(!vis[tamp]){
vis[tamp]=;
ans[i]=tamp;
}
else{
int flag3=;
for(int j=;j<n;++j)
if(!vis[(tamp+j*j)%m]){
vis[(tamp+j*j)%m]=;
ans[i]=(tamp+j*j)%m;
flag3=;
break;
}
if(!flag3)
ans[i]=-;
}
}
for(int i=;i<=n;++i){
if(ans[i]==-)
cout<<"-";
else
cout<<ans[i];
if(i<n)
cout<<" ";
}
return ;
}