PAT 1078 Hashing

PAT 1078 Hashing

算是知道quadratic probing是个啥了。。

二次探测：
在要插入的位置a开始
每次加
也就是每次的探测位置是
不是在上一次的基础上+step*step，是在最初地址的基础上加

#include<bits/stdc++.h> 
using namespace std;
const int N=1e6+10;
typedef long long LL;

bool he[N];
bool inhash[N];
int primes[N];

int main(){
    he[0]=he[1]=true;
    int cnt=0;
    for(int i=2;i<=N-1;i++){
        if(!he[i])primes[cnt++]= i;
        for(int j=0;primes[j]<=(N-1)/i;j++){
            he[primes[j]*i]=true;
            if(i % primes[j]==0)break;
        }
    }
    int msize,n;
    cin>>msize>>n;
    
    //找新的msize 
    for(int i=msize;i<N-1;i++){
        if(!he[i]){
            msize=i;
            break;
        }
    }
    
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        if(i)cout<<" ";
        if(!inhash[x%msize]){
            inhash[x%msize]=true;
            cout<< x%msize;
        }
        else {
            int start=x%msize;
            int step;
            for( step=1;step<msize;step++){
                int pos=(start+step*step)%msize;
                if(!inhash[pos]){
                    inhash[pos]=true;
                    cout<<pos;
                    break;
                }
            }
            if(step>=msize){
                cout<<"-";
            }
        }
    }
    
    return 0;
}