AcWing 1564. 哈希
原题链接
简单
作者:
ACkingyk
,
2023-11-14 23:07:02
,
所有人可见
,
阅读 42
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e4;
int h[10010];
int msize,n;
/*
哈希存储之正向探测法:
正向探测法 : k = (num+i*i)%msize (i: 0~msize)
*/
bool judge(int x)//判断msize是否为质数
{
if(x==1) return false;
for(int i=2;i<=x/i;i++) if(x%i==0) return false;
return true;
}
int change(int x)//将msize改变为大于原来的最小质数
{
for(int i=x+1;i<=100003;i++)
{
if(judge(i)) return i;
}
}
void insert(int x)//查找插入哈希表的位置
{
for(int i=0;i<msize;i++)
{
int k = (x+i*i)%msize;
if(h[k]==-1)
{
h[k] = x;
cout << k << " ";
return ;
}
}
cout << "- ";
return ;
}
int main()
{
scanf("%d%d",&msize,&n);
if(!judge(msize)) msize = change(msize);
memset(h,-1,sizeof h);
while(n--)
{
int num;
scanf("%d",&num);
insert(num);
}
}