题目链接：点击打开链接
题目大意：略。
解题思路：平方探测法处理哈希表，但是该题只能正增长：with positive increments only。即，hi=(h(key)+i*i)%m （0 ≤ i ≤ m-1）
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; typedef long long ll; int isPrime(int x) { if(x<2) return 0; int len=sqrt(x); for(int i=2;i<=len;i++) if(x%i==0) return 0; return 1; } int vis[20000]; int main() { int p,n,a,idx,f; scanf("%d%d",&p,&n); while(!isPrime(p)) p++; vector<int> v; for(int i=0;i<n;i++) { scanf("%d",&a); f=0; for(int j=0;j<p;j++) { idx=abs(a+j*j)%p; if(!vis[idx]) { v.push_back(idx); vis[idx]=1; f=1; break; } // idx=abs(a-j*j)%p; // if(!vis[idx]) // { // v.push_back(idx); // vis[idx]=1; // f=1; // break; // } } if(!f) v.push_back(-1); } for(int i=0;i<v.size()-1;i++) { if(v[i]!=-1) printf("%d ",v[i]); else printf("- "); } if(v[v.size()-1]!=-1) printf("%d\n",v[v.size()-1]); else printf("-\n"); return 0; }
