原题链接：https://www.nowcoder.com/pat/5/problem/4308
#pragma warning(disable:4996) #include<iostream> #include<algorithm> using namespace std; int k[10005]; int N, MSize; bool visited[10005]; /* 题目总结：主要两个考点 1）判断质数和找下一个质数 (1)注意处理1和2 (2)注意质数n 不能从2到被sqrt(n)+1 整除 可以提高一点点效率 2）哈希表 （1）避免冲突，这里用的是平方探测法，裂开，一开始忘了相关的知识，quadratic probing又比较陌生 以为冲突就是输出- (2) 这里顺便再复习一下 常见的散列函数：除留余数法，直接定址法，数值分析法，平方取中法 解决冲突的方法：拉链法，开放定址法（线性 平方 伪随机），再散列法 */ // 判断质数 bool is_prime(int n) { int sq = (int)sqrt(n); for (int i = 2; i < sq+1; i++) { if (n%i == 0) { return false; } } return true; } // 返回一个比n大的最小素数,可能n本身就是素数 int next_prime(int n) { if (n == 1 || n == 2)return 2; if (is_prime(n))return n; while (!is_prime(++n)); return n; } int main() { cin >> MSize >> N; int key; int table_size = next_prime(MSize); for (int i = 0; i < N; i++) { cin >> k[i]; int j = 0; for (; j < table_size; j++) { key = (k[i]+j*j) % table_size; if (!visited[key]) { printf("%d", key); visited[key] = true; break; } } if (j == table_size)printf("-"); if (i != N - 1)printf(" "); } system("pause"); return 0; }
