1078 Hashing (25 分)

單詞積累

Quadratic probing (with positive increments only) 平方探測法（僅有正數(shù)增序）

prime 素數(shù)

思路

考察的點比較清晰

1. 素數(shù)判定：關(guān)鍵考慮特殊點： 1不是素數(shù)， 2是素數(shù)，因數(shù)求到 i * i < number，比用sqrt更好，固定模板 建議熟記
2. 哈希表 沖突解決方法：平方探測 （number + i * i）% m (i從1到m)

代碼

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

int m, n;
const int maxn = 10004;
map<int, int> mp;

bool isprime(int a) {
    if (a == 1) return false;
    for (int i = 2; i * i <= a; i++) {
        if (a % i == 0) return false;
    }
    return true;
}

int main() {
    cin>>m>>n;
    if (!isprime(m)) {
        while (!isprime(m)) {
            m++;
        }
    }
    for (int i = 0; i < n; i++) {
        int number;
        cin>>number;
        int flag = 0;
        for (int j = 0; j <= m; j++) {
            int pos = (number + j * j) % m;
            if (mp.find(pos) == mp.end()) {
                cout<<pos % m;
                flag = 1;
                if (i != n - 1) cout<<" ";
                mp[pos] = 1;
                break;
            }
        }
        if (flag == 0) {
            cout<<"-";
            if (i != n - 1) cout<<" ";
        }
    }
}