5-17 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 $\% TSizeH(key)=key%TSizewhere TSizeTSize is the maximum size of the hash table. Quadratic probing (with positive increments only) is used to solve the collisions.$

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: $10^4≤104) and NN (le MSize≤MSize) which are the user-defined table size and the number of input numbers, respectively. Then NN distinct positive integers are given in the next line. All the numbers in a line are separated by a space.$

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.

Sample Input:

4 4
10 6 4 15

Sample Output:

0 1 4 -

/*
 * 这题就是除留余数法插入 平方探测法解决冲突（这里只有正向） 实现散列表。
*/
#include "iostream"
#include "cmath"
using namespace std;
#define MAXSIZE 20000 /* 带进去算了下这区间有素数 10006 我也是试着取得0..0.。*/
int nextPrime(int n) {
    int i, j;
    bool flag = true;
    if (n % 2 == 0)
        n++;
    if (n == 1) /* 判断素数要注意1啊~ 在这里卡了2次- - */
        return 2;
    for (i = n; i < MAXSIZE; i+=2) {
        int k = sqrt(i);
        for (j = 2; j<=k ; j++) 
            if (!(i%j))
                break;
        if (j > k)
            return i;
    }
    return i;
}

int val[10001];
void find(int a[],int m,int n) {
    int i, j;
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            int pos = (val[i]%n + j*j) % n;
            if (a[pos] == val[i])
            {
                if (i == 0)
                    cout << pos;
                else
                    cout << " " << pos;
                break;
            }
        }
        if (j == n)
            if (i == 0) {
                cout << "-";
            }
            else {
                cout << " " << "-";
            }
    }
}

void insert(int n,int m,int a[]) {
    for (int i = 0; i < m; i++) {
        cin >> val[i];
        for (int j = 0; j < n; j++) {
            int pos = (val[i]%n + j*j) % n;
            if (!a[pos]) {
                a[pos] = val[i];
                break;
            }
        }
    }
}
int main() {
    int n, m;
    int a[20001];
    cin >> n >> m;
    n = nextPrime(n);
    for (int i = 0; i < n; i++)
        a[i] = 0;
    insert(n, m, a); /* 映射 */
    find(a, m, n);
    cout << endl;
    return 0;
}