Hashing

题面

参见 https://www.patest.cn/contests/pat-a-practise/1078

说明

使用二次探测法进行探测，公式为pos=(input+i^2)%size其中i从0开始计数
注意对于输入的大小M，需要先把M转化为大于M的最小素数

代码

#include <iostream>
#include <cstring>
using namespace std;
bool isPrime(int x) {
    if (x == 1)return false;
    if (x == 2 || x == 3)return true;
    for (int i = 2; i*i <=x; i++)
    {
        if (x%i == 0)return false;

    }
    return true;
}
bool flag[10000];
int main() {
    int m, n, input;//m是大小
    cin >> m >> n;
    while (!isPrime(m))
    {
        m++;
    }
    while(n--)
    {
        cin >> input;
        bool inserted = false;
        for (int j = 0; j < m; j++) {
            int position = (input + j*j) % m;
            if (!flag[position])
            {
                inserted = true;
                flag[position] = true;
                cout << position << (n ? " " :"\n");
                break;
            }
        }
        if (!inserted) {
            cout<<"-"<< (n ? " " : "\n");
        }
    }
    return 0;
}