7-21 Hashing (25分)（平方探查法）

题目：

分析：

num[i]用于存放数值
首先要判断输入的初始m是否为素数，如果不是素数，需要将m增加到素数
确定了m之后，判断pos = num[i] % m这个位置在hashTable中是否已经被访问了，如果vis[pos]为false，说明此位置未被访问直接输出即可，如果为true，说明此位置已经被访问了，之后运用平方探查法找合适的位置，具体的做法是 nexPos = (pos + j*j) % m(j从1到m-1遍历)，在遍历的过程中，如果含有nexPos未被访问，则将此位置填充，输出即可，如果 j 到了m之后还没有找到合适的位置，输出 - 即可

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

const int MAXN = 1e5+5;
int m,n;
int num[MAXN];
bool vis[MAXN];

void GetPrime()
{
    bool flag = false;
    while(1)
    {
        for(int i=2;i<=sqrt(m);++i)
            if(m % i == 0)
            {
                flag = true;
                break;
            }
        if(flag)
        {
            m++;
            flag = false;
        }
        else break;
    }
    return;
}

int main()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&num[i]);
    if(m!=2&&m!=1&&m!=0)
        GetPrime();
    if(m == 1|| m == 0) m = 2;
    for(int i=1;i<=n;++i)
    {
        int pos = num[i]%m;
        if(i < n)
        {
            if(!vis[pos])
            {
                printf("%d ",pos);
                vis[pos] = true;
            }
            else
            {
                int nexPos,j;
                for(j=1;j<=m-1;++j)
                {
                    nexPos = (pos + j*j) % m;
                    if(!vis[nexPos])
                    {
                        printf("%d ",nexPos);
                        vis[nexPos] = true;
                        break;
                    }
                }
                if(j==m)
                    printf("- ");
            }
        }
        if(i == n)
        {
            if(!vis[pos])
            {
                printf("%d\n",pos);
                vis[pos] = true;
            }
            else
            {
                int nexPos,j;
                for(j=1;j<=m-1;++j)
                {
                    nexPos = (pos + j*j) % m;
                    if(!vis[nexPos])
                    {
                        printf("%d\n",nexPos);
                        break;
                    }
                }
                if(j==m)
                    printf("-\n");
            }
        }
    }
    return 0;
}