P5445 - 基础实验5-2.1：整型关键字的平方探测法散列

内存限制：128 MB 时间限制：1.000 S

评测方式：文本比较命题人：

提交：46 解决：15

本题的任务很简单：将给定的无重复正整数序列插入一个散列表，输出每个输入的数字在表中的位置。所用的散列函数是 $H (k ey) = k ey % TS i ze$ ，其中 $TS i ze$ 是散列表的表长。要求用平方探测法（只增不减，即 $H (Key) + i ²$ ）解决冲突。

注意散列表的表长最好是个素数。如果输入给定的表长不是素数，你必须将表长重新定义为大于给定表长的最小素数。

首先第一行给出两个正整数

MS i ze

（

\leq 1 0^4

）和

N

（

\leq MS i ze

），分别对应输入的表长和输入数字的个数。随后第二行给出

N

个不重复的正整数，数字间以空格分隔。

在一行中按照输入的顺序给出每个数字在散列表中的位置（下标从 0 开始）。如果某个数字无法插入，就在其位置上输出 -。输出间以 1 个空格分隔，行首尾不得有多余空格。

4 4
10 6 4 15

0 1 4 -

数据结构

5445: 基础实验5-2.1：整型关键字的平方探测法散列