1078 Hashing (25分)

1078 Hashing (25分)

思路

没看到题目中的：

Quadratic probing (with positive increments only)

直接暴力，用$vis$存下就好了。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e4,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int n,m,vis[N],ans[N];
int main(){
    cin>>n>>m;if(n<=1) n=2;
    for(int i=n;;i++){
        int f=1;
        for(int j=2;j*j<=i;j++){
            if(i%j==0){
                f=0;break;
            }
        }
        if(f) {
            n=i;break;
        }
    }
    //printf("n=%d\n",n);
    for(int i=1,x;i<=m;i++){
        scanf("%d",&x);
        if(vis[x%n]){
            int f=0;
            for(int j=1;j<n;j++){
                if(!vis[(x+j*j)%n]){
                    vis[(x+j*j)%n]=1;
                    ans[i]=(x+j*j)%n;
                    f=1;break;
                }
            }
            if(!f) ans[i]=-1;
        }
        else vis[x%n]=1,ans[i]=x%n;
        if(~ans[i]) printf("%d",ans[i]);
        else printf("-");
        if(i<m) printf(" ");
        else printf("\n");
    }
    return 0;
}