题目给定一个哈希表的长度、插入的元素以及要进行查找的元素，采用除留余数法作为哈希函数，使用平方探测法解决冲突，要求无法再哈希表中插入的元素以及平均查找长度。
每个输入文件包含一个测试用例。对于每种情况，第一行均包含 3 个正数：MSize，N 和 M，分别是用户定义的表大小、输入关键字个数和要查找的关键字个数。在下一行中给出 N 个不同的正整数，在下一行中给出 M 个正整数键。一行中的所有数字均以空格隔开。
对于每个测试用例，如果无法插入一些数字，则打印一行X cannot be inserted.，其中 X 是输入数字。最后一行打印平均查找时间，精确到小数点后 1 位。
由于给定的表长不会超过$10^4$，而且要求哈希表的实际表长是一个不小于给定表长的素数，可以用埃氏筛法先生成一张$10^5$的素数表，然后找出不小于给定表长的素数作为实际表长。通过将给定元素值对表长的余数作为在哈希表中的插入位置，如果出现冲突，采用平方探查法解决。平方探查法的具体过程是，假设给定元素值为 a，表长为 MSize，插入位置为$a%MSize$，假设$a%MSizeSize$位置已有元素，即发生冲突，则查找$(a+1^2)%MSize$，$(a-1^2)%MSize$，$(a+2^2)%MSize$，$(a-2^2)%MSize$，$\cdots\cdots$，$(a+MSize^2)%MSize$，$(a-MSize^2)%MSize$ 直至查找到一个可进行插入的位置，否则当查找到$(a+MSize^2)%MSize$，$(a-MSize^2)%MSize$ 仍然不能插入则该元素插入失败。另外题目要求平方探测只需正向探测即可，也就是说，当发生冲突的时候，只需查找$(a+1^2)%MSize$，$(a+2^2)%MSize$，$\cdots\cdots$，$(a+MSize^2)%MSize$即可。同样地，进行查找时也采取相同的方法进行查找，当查找到的当前位置没有元素或查找到$(a+MSize^2)%MSize$位置还未查找到时，则查找失败；当查找到的当前位置元素与查找元素相等，即查找成功。没探测到一个位置查找长度则增长 1，求出总的查找长度再除以查找元素个数即可。
#include <bits/stdc++.h>
using namespace std;
using gg = long long;
vector<gg> prime;
void getPrime(gg n = gg(1e5)) {
vector<bool> f(n + 5);
for (gg i = 2; i <= n; ++i)
if (not f[i]) { // i 没有被筛去
prime.push_back(i);
for (gg j = i + i; j <= n; j += i) //筛去 i 的所有倍数
f[j] = true;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
getPrime();
gg ni, mi, ki, ai;
cin >> mi >> ni >> ki;
mi = *lower_bound(prime.begin(), prime.end(), mi);
vector<gg> table(mi);
for (gg i = 0; i < ni; ++i) {
cin >> ai;
gg k = ai % mi;
for (gg j = 0; j <= mi and table[k] != 0; ++j) {
k = (ai + j * j) % mi;
}
if (table[k] == 0) {
table[k] = ai;
} else {
cout << ai << " cannot be inserted.\n";
}
}
gg ans = 0;
for (gg i = 0; i < ki; ++i) { //统计要进行查找的元素的总查找长度
cin >> ai;
gg k = ai % mi, j = 0;
while (j <= mi and table[k] != 0 and table[k] != ai) {
++j;
k = (ai + j * j) % mi;
}
ans += j > mi ? j : j + 1;
}
cout << fixed << setprecision(1) << ans * 1.0 / ki;
return 0;
}