注意是平方探测,1^2,2^2,3^2.....其中要平方的数小于TSize,不然探测没法停止,我之前在这里卡着过不了。
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <algorithm> #include <cmath> #include <string> #include <cstring> using namespace std; bool is_prime(int n) { if (n == 0 || n == 1) return false; if (n == 2) return true; int bound = (int)sqrt(n); for (int i = 2; i <= bound; i++) { if (n % i == 0) return false; } return true; } int get_TSize(int MSize) { for (int i = MSize;; i++) { if (is_prime(i)) return i; } } int main() { freopen("in.txt", "r", stdin); int MSize, N; cin >> MSize >> N; int TSize = get_TSize(MSize); int *flag = new int[TSize]; // bool *flag = new bool[TSize]; memset(flag, 0, sizeof(flag) * TSize); for (int i = 0; i < N; i++) { int tmp; cin >> tmp; int pos = tmp % TSize; if (i == 0) { flag[pos] = true; cout << pos; } else { if (flag[pos]) { bool inst = false; for (int ins = 1;ins < TSize; ins++) { if (!flag[(pos + ins*ins) % TSize]) { inst = true; flag[(pos + ins*ins) % TSize] = true; cout << " " << (pos + ins * ins) % TSize; break; } } if (!inst) cout << " -"; } else { flag[pos] = true; cout << " " << pos; } } } cout << endl; }