题目：https://pintia.cn/problem-sets/994805342720868352/problems/994805389634158592

注意点：二次探查法的边界是tsize，step = tsize的时候就是查找失败的时候。

代码部分

  1. #include<algorithm>
  2. #include<vector>
  3. #include<iostream>
  4. using namespace std;
  6. const int maxn = 100010;
  7. vector<bool> is_prime(maxn, true);
  8. void get_prime(){
  9.     is_prime[1] = false;
  10.     for(int i = 2; i < maxn; i++){
  11.         if(is_prime[i]){
  12.             for(int j = 2 * i; j < maxn; j += i){
  13.                 is_prime[j] = false;
  14.             }
  15.         }
  16.     }
  17. }
  19. int main(){
  20.     int tsize, n, temp;
  21.     get_prime();
  22.     scanf("%d%d", &tsize, &n);
  23.     //更新tsize
  24.     if(is_prime[tsize] == false){//如果不是素数
  25.         for(int i = tsize; i < maxn; i++){
  26.             if(is_prime[i]) {
  27.                 tsize = i;
  28.                 break;
  29.             }
  30.         }
  31.     }
  33.     vector<int> hashtable(tsize, -1);
  34.     for(int i = 0; i < n; i++){
  35.         scanf("%d",&temp);
  36.         if(hashtable[temp % tsize] == -1){
  37.             hashtable[temp % tsize] = temp;
  38.             printf("%d", temp % tsize);
  39.         } else {
  40.             int step = 1;
  41.             while(step < tsize){
  42.                 if(hashtable[(temp + step * step) % tsize] == -1){
  43.                     hashtable[(temp + step * step) % tsize] = temp;
  44.                     printf("%d",(temp + step * step) % tsize);
  45.                     break;
  46.                 } else step++;
  47.             }
  48.             if(step == tsize) printf("-");
  49.         }
  50.         if(i != n - 1) printf(" ");
  51.     }
  52.     return 0;
  53. }