1078. Hashing (25) 二次方探查法

#include <iostream>
const int maxn = 10001;
bool isprime(int a) {
    if(a == 1) return false;//素数为大于1且能被除了自身和1整除的数
    for(int i = 2; i * i <= a; i++)
        if(a % i == 0)
            return false;
    return true;
}
int func(int a) {//求下一个素数
    while(isprime(a) == false) a++;
    return a;
}
bool hashTable[maxn];
int main() {
    int MSize, n, key;
    scanf("%d %d", &MSize, &n);
    int size = func(MSize);
    for(int i = 0; i < n; i++) {
        scanf("%d", &key);//key wao
        int index = key % size;
        if(hashTable[index] == false) {
            hashTable[index] = true;
            if(i != 0) printf(" ");//在线处理
            printf("%d", index);
        } else {
            int flag = 0;
            for(int step = 1; step < size; step++) {//Quadratic probing
                index = (key + step * step) % size;//key wao
                if(hashTable[index] == false) {
                    hashTable[index] = true;
                    flag = 1;
                    if(i != 0) printf(" ");
                    printf("%d", index);
                    break;
                }
            }
            if(flag == 0) {
                if(i != 0) printf(" ");
                printf("-");
            }
        }
    }
    return 0;
}