11-散列2 Hashing (25分)

The task of this problem is simple: insert a sequence of distinct positive integers into a hash table, and output the positions of the input numbers. The hash function is defined to be H(key)=key%TSize where TSize is the maximum size of the hash table. Quadratic probing (with positive increments only) is used to solve the collisions.
这个问题的任务很简单：将一个不同的正整数序列插入到哈希表中，然后输出输入数字的位置。哈希函数定义为H（key）= key％TSize，其中TSize是哈希表的最大大小。二次探测（仅具有正增量）用于解决冲突。

Note that the table size is better to be prime. If the maximum size given by the user is not prime, you must re-define the table size to be the smallest prime number which is larger than the size given by the user.
请注意，表大小最好是素数。如果用户给出的最大大小不是素数，则必须将表大小重新定义为最小的素数，该最小素数大于用户给出的大小。

Input Specification:

Each input file contains one test case. For each case, the first line contains two positive numbers: MSize (≤10^4) and N (≤MSize) which are the user-defined table size and the number of input numbers, respectively. Then N distinct positive integers are given in the next line. All the numbers in a line are separated by a space.
每个输入文件包含一个测试用例。对于每种情况，第一行均包含两个正数：MSize（≤10^4）和N（≤MSize）分别是用户定义的表大小和输入数字的数量。然后在下一行中给出N个不同的正整数。一行中的所有数字都用空格分隔。

Output Specification:

For each test case, print the corresponding positions (index starts from 0) of the input numbers in one line. All the numbers in a line are separated by a space, and there must be no extra space at the end of the line. In case it is impossible to insert the number, print “-“ instead.
对于每个测试用例，在一行中打印输入数字的相应位置（索引从0开始）。一行中的所有数字均以空格分隔，并且行尾不得有多余的空格。如果无法插入数字，请打印“-”。

Sample Input:

4 4
10 6 4 15

Sample Output:

0 1 4 -

解析

哈希表长是比原表大的最小素数：例如原表是4，则哈希表为5
用数组存储，输入数除余后，检测所在数组位置是否被占用，如果被占用，则每次用余数加i的平方（i从1开始），如果全不合适，就输出“-”

代码

#include<bits/stdc++.h>
using namespace std;

int size(int x){
    if(x==1)
        return 2;
    int p,flag;
    p=x;
    while(1){
        flag=1;
        for(int i=2;i<=sqrt(x);i++){
            if(p%i==0){
                flag=0;
                break;
            }
        }
        if(flag==0){
            p+=1;
        }else{
            return p;
        }
    }
}
int get(int key,int n){
    return key%n;
}
int main(){
    int n,m;
    cin>>n>>m;
    n=size(n);    //大于表长最大的素数 
    
    int a[n],x,pos,tempx;
    memset(a,-1,sizeof(a));
    
    for(int i=0;i<m;i++){
        if(i!=0)
            cout<<" "; 
            
        cin>>x;
        pos=get(x,n);
        tempx=pos;
    
        
        if(a[tempx]==-1){    //验证所在位置是否为空 
            a[tempx]=x;
            cout<<pos;
        }else{
            int cnt,flag=0;
            for(cnt=1;cnt<n;cnt++){
                pos=get(tempx+cnt*cnt,n);    //判断其他位置是否可以插入 
                if(a[pos]==-1){
                    flag=1;
                    a[pos]=x;
                    cout<<pos;
                    break;
                }
            }
            if(flag==0){
                cout<<"-";
            }
        }
    }
    return 0;
}