PAT.A1078 Hashing

題意

樣例（可複制）

4 4
10 6 4 15
//output
0 1 4 -      

注意點

1. Quadratic probing是指二次方探查法，即當H(a)發生沖突時，讓a按a+1^2 , a-1^2 ,a+2^2 ,a-2^2 ,a+3^2 , a-3^2 的順序調整a的值。本題中已經說明隻要往正向解決沖突，是以需要按a+1^2 ,a+2^2 ,a+3^2的順序調整a的值。
2. 沖突處理公式是M= (a+ step * step) % TSize,有些讀者可能會沒有模上TSize。
3. 1号測試點“答案錯誤”的原因是:判斷質數時把1也當成了質數。
4. 最後一個測試點“運作逾時”的原因是:程式當中出現了死循環
5. 出現“格式錯誤”的需要注意，在最後一個輸出結束後不能有空格。

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

int Hash[10010]={0};
bool isprime(int a){
    if(a<=1)return false;
    int sqr=(int)sqrt(1.0*a);
    for(int i=2;i<=sqr;i++)
        if(a%i==0)return false;
    return true;
}
int main(){
    int ts,n,tmp;
    cin>>ts>>n;
    while(!isprime(ts))ts++;
    for(int i=0;i<n;i++){
        scanf("%d",&tmp);
        if(i>0)printf(" ");
        int m=tmp%ts;
        if(Hash[m]){
            int j;
            for(j=1;j<ts;j++){
                int pos=(m+j*j)%ts;
                if(!Hash[pos]){
                    Hash[pos]=1;
                    printf("%d",pos);
                    break;
                }
            }
            if(j==ts)printf("-");
        }else{
            Hash[m]=1;
            printf("%d",m);
        }
    }
    return 0;
}