PAT甲级1078 hashing-蒲公英云

PAT甲级1078 hashing

题目大意：
利用除留余数法建hashtable，然后利用平方探查法缓解hash值冲突问题，然后要你输出每个输入的值在hashtable中的下标位置，如果不存在的话输出 -
解题思路：
1.当给的表长msize不为素数时，需要先求出比msize大的最小的素数
2.如果temp%msize的位置已经有元素，那么对H(key)+k*k位置进行查找，如果H(key)+k *k大于msize，则取模msize。若没找到合适的位置则递增k，当k在【0，msize）范围内都没有找到一个合适的位置的话，那么temp无法插入hashtable，输出-
注意：
大于10000的最小素数为止，所以在利用素数筛选法的时候尽量把数组开大一点
代码：

#include<cstdio>
#include<vector>
using namespace std;
int main()
{ 
    int msize,n;
    scanf("%d%d",&msize,&n);
    int isprime[10099];//1表示是素数,不够的话增加范围，适用最后一个测试案例
    for(int i=0;i<10099;i++)isprime[i]=1;
    isprime[1]=0;
    for(int i=2;i<6000;i++)//素数筛查法
    { 
        if(isprime[i]==1)
        { 
            for(int j=i*2;j<10099;j+=i)isprime[j]=0;
        }
    }
    while(isprime[msize]!=1)msize++;
    vector<int> v(msize,-1),output(n);
    for(int i=0;i<n;i++)
    { 
        int temp,k=0;
        bool flag=false;
        scanf("%d",&temp);
        while(k<msize)
        { 
            int index=temp+k*k;
            if(index>=msize)index=index%msize;//判定条件很关键
            if(v[index]==-1)//未被占用
            { 
                output[i]=index;
                v[index]=temp;
                flag=true;
                break;
            }
            else k++;
        }
        if(!flag)output[i]=-1;
    }
    printf("%d",output[0]);
    for(int i=1;i<n;i++)
    { 
        if(output[i]!=-1)printf(" %d",output[i]);
        else printf(" -");
    }
    return 0;
}