1. 原題： https://www.patest.cn/contests/pat-a-PRactise/1078

2. 思路：

3. 源碼：

#include<iostream>#include<algorithm>//使用sqrt函數#include<vector>using namespace std;int N, len;//分別為元素個數， 給定的散列表長度vector<int> flag;//標記是否有元素int isPrime(int x);//是否素數int getSize(int x);//求出散列表長度int hashKey(int x);//求散列地址int main(void){	//freopen("in.txt", "r", stdin);	scanf("%d %d", &len, &N);	len = getSize(len);//求出表長度	flag.resize(len, 0);	int key, pos;//分別為元素值， 散列地址	for (int i = 0; i < N; i++)	{		if (i != 0)			printf(" ");		scanf("%d", &key);		pos = hashKey(key);		if (pos == -1)//無法散列			printf("-");		else			printf("%d", pos);	}	printf("/n");	return 0;}int isPrime(int x)//是否素數{	if (x == 1)		return 0;	for (int i = 2; i <= (int)sqrt(x); i++)	{		if (x % i == 0)			return 0;	}	return 1;}int getSize(int x)//求出散列表長度{	if (isPrime(x) == 1)		return x;	int i;	for (i = x + 1; i; i++)	{		if (isPrime(i) == 1)			break;	}	return i;}int hashKey(int x)//求散列地址{	int val = x % len;//散列地址	if (flag[val] == 0)//表示該地址為空	{		flag[val] = 1;		return val;	}	int cnt = 0;//記錄沖突次數	int k = 0;	while (k <= len / 2)//平方探測法的最大增量	{		cnt++;		if (cnt % 2 == 1)//奇數次沖突		{			k++;			val = (val + k*k) % len;		}		else//偶數次沖突		{			val -= k*k;			while (val < 0)//使得val符合正常范圍				val += len;		}		if (flag[val] == 0)		{			flag[val] = 1;			return val;		}	}	return -1;//無法散列}