关于二次探测为什么只需要探测m次的问题
在二次探测的时候,k 只从 0 到 m-1 探测了m次
因为
(k * k) % m 是以m个数为循环出现的
比如 m 取 5 时
0*0 % 5 = 0
1*1 % 5 = 1
2*2 % 5 = 4
3*3 % 5 = 4
4*4 % 5 = 1
...
5*5 % 5 = 0
6*6 % 5 = 1
所以可能的位置最多只有m个
可证明:
$$
((k+m)*(k+m)) \% m == (k * k) \% m
$$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
bool is_prime[N], st[N];
int h[N];
int m, n;
void init(){
for(int i = 2; i < N; i++){
if(!st[i]){
is_prime[i] = true;
for(int j = i * 2; j < N; j += i) st[j] = true;
}
}
}
int find(int x){
int t = x % m;
for(int k = 0; k < m; k++){
int i = (t + k * k) % m;
if(h[i] == 0) return i;
}
return -1;
}
int main(){
init();
cin >> m >> n;
while(!is_prime[m]) m++;
for(int i = 0; i < n; i++){
int a; cin >> a;
int pos = find(a);
if(pos == -1) cout << "- ";
else {cout << pos << " "; h[pos] = a;}
}
return 0;
}
终于找到一篇解决为啥只需要探测m次的题解了,感谢!