题解 CF1622F【Quadratic Set】
Calculatelove
·
·
题解
CF1622F。
Description
给出一个集合 A = \{1, 2, ..., n\} = \{x \in \mathbb{Z} \mid 1 \leq x \leq n\}。
你需要寻找一个非空集合 A' \subseteq A，使得 \prod_{k \in A'} k! 是一个完全平方数。
在此基础上，你需要最大化 |A'|，并以任意顺序给出集合 A' 中的所有数。
数据范围：1 \leq n \leq 10^6。
时空限制：4000 \ \mathrm{ms} / 256 \ \mathrm{MiB}。
Solution
结论
至少存在一个方案，使得集合 A 中不选的数的个数 \leq 3。
证明
假设现在给出任意一个正整数 k，考察下式：
\begin{aligned}
\prod\limits_{i = 1}^{2k} i! & = \prod\limits_{i = 1}^k (2i - 1)! \cdot (2i)! \\
& = \prod\limits_{i = 1}^k \left((2i - 1)!\right)^2 \cdot 2i \\
& = \left( \prod\limits_{i = 1}^k (2i - 1)! \right)^2 \cdot 2^k \cdot k!
\end{aligned}
- 对于 n \equiv 0 \pmod 4，可以取 A' = A \setminus \left\{ \frac{n}{2} \right\}。
- 对于 n \equiv 2 \pmod 4，可以取 A' = A \setminus \left\{2, \frac{n}{2}\right\}。
- 对于 n \equiv 1 \pmod 2，可以先不取 n 这个数，然后转换为上述两种情况之一。
Q.E.D.
现在有了很优秀的构造解，但注意到该解不一定是最优解，还要处理集合 A 中不选的数恰好为 0, 1, 2 时的解。
考虑完全平方数的本质：在唯一分解形式下，所有质因子的次数均为偶数。这时候就可以考虑使用 xor hashing。
定义完全异或性哈希函数 f(x)，一开始先给 1 \sim n 中的所有质数 p 的 f(p) 赋一个范围较大的随机数，其他的合数的 f(x) 定义为 x 所有质因子的 f 函数的异或和（多个相同质因子需要重复异或），特别地 f(1) = 0。在这样的定义下，x 为完全平方数当且仅当 f(x) = 0。
记 $P = f(1!) \bigoplus f(2!) \bigoplus \cdots \bigoplus f(n!)$。
- 对于所有都选的情况，判断 $P$ 是否为 $0$ 即可。
- 对于不选 $1$ 个数的情况，相当于判断是否存在一个 $i$ 使得 $P \bigoplus f(i!) = 0$，枚举即可。
- 对于不选 $2$ 个数的情况，相当于判断是否存在一对 $i,j$ 使得 $P \bigoplus f(i!) \bigoplus f(j!) = 0$，可以先将所有 $f(j!)$ 的值存入一个哈希表或 `std::map`，再在这个容器中查找 $P \bigoplus f(i!)$ 即可。
实现的较好可以做到 $\mathcal{O}(n)$。
```c++
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <ctime>
#include <random>
#include <unordered_map>
typedef long long s64;
const int N = 1e6 + 10;
const s64 L = 1152921504606846976LL;
int n;
int k, prime[N], fac[N];
s64 f[N], S[N];
std::mt19937_64 rnd(time(0));
std::uniform_int_distribution<long long> dist(0, L - 1);
void sieve(int N) {
f[1] = 0;
for (int i = 2; i <= N; i ++) {
if (!fac[i]) fac[i] = i, prime[++ k] = i, f[i] = dist(rnd);
for (int j = 1; j <= k; j ++) {
if (prime[j] > fac[i] || prime[j] > N / i) break;
fac[i * prime[j]] = prime[j];
f[i * prime[j]] = f[i] ^ f[prime[j]];
}
}
for (int i = 1; i <= N; i ++)
S[i] = S[i - 1] ^ f[i];
}
std::unordered_map<s64, int> List;
int cnt;
bool mark[N];
void output() {
printf("%d\n", cnt);
for (int i = 1; i <= n; i ++) {
if (mark[i]) continue;
printf("%d ", i);
}
}
int main() {
freopen("square.in", "r", stdin);
freopen("square.out", "w", stdout);
scanf("%d", &n);
sieve(n);
s64 P = 0;
for (int i = 1; i <= n; i ++) P ^= S[i];
if (P == 0) {
cnt = n, output();
return 0;
}
for (int i = 1; i <= n; i ++)
if ((P ^ S[i]) == 0) {
cnt = n - 1, mark[i] = 1, output();
return 0;
}
for (int i = 1; i <= n; i ++)
List[S[i]] = i;
for (int i = 1; i <= n; i ++)
if (List.count(P ^ S[i])) {
int j = List[P ^ S[i]];
cnt = n - 2, mark[i] = 1, mark[j] = 1, output();
return 0;
}
cnt = n - 3, mark[2] = 1, mark[(n - 1) / 2] = 1, mark[n] = 1, output();
return 0;
}
```