1078 Hashing (二次探测法)

1078 Hashing (25分)

最后一个测试点，需要二次方探测法。
二次方探测法，探测时

 int tsize,ans;
 for(tsize=1;tsize<=Tsize;tsize++)
 {
    ans=(x[i]+(tsize*tsize))%Tsize;
 }

#include <iostream>
#include <algorithm>
using namespace std;
const int MAX=1e5+20;
const int INF=0x3f3f3f3f;
int book[MAX],x[MAX];
bool isprime(int x)
{
    if(x<=1)
        return false;
    for(int i=2;i<=(int)sqrt(1.0*x);i++)
    {
        if(x%i==0)
            return false;
    }
    return true;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    while(isprime(n)==false)
        n++;
    for(int i=0;i<m;i++)
    {
        scanf("%d",&x[i]);
    }
    for(int i=0;i<m;i++)
    {
        int num=x[i]%n;
        if(book[num]==0)
        {
            book[num]=1;
            if(i==0)
                printf("%d",num);
            else
                printf(" %d",num);
        }
        else
        {
            int tsize,ans;
            for(tsize=1;tsize<=n;tsize++)
            {
                ans=(x[i]+(tsize*tsize))%n;
                if(book[ans]==0)
                {
                    book[ans]=1;
                    if(i==0)
                        printf("%d",ans);
                    else
                        printf(" %d",ans);
                    break;
                }
            }
            if(tsize>n)
            {
                if(i==0)
                    printf("-");
                printf(" -");
            }
        }
    }
    return 0;
}