PAT 甲级 刷题日记|A 1078 Hashing (25

1078 Hashing (25 分)

单词积累

Quadratic probing (with positive increments only) 平方探测法（仅有正数增序）

prime 素数

思路

考察的点比较清晰

1. 素数判定：关键考虑特殊点： 1不是素数， 2是素数，因数求到 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<<" ";
        }
    }
}