「CF1622F」Quadratic Set
给出一个集合 A = \{1, 2, \dots, 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。
时空限制:4s / 256MiB。
Solution
结论
至少存在一个方案,使得集合 A 中不选的数的个数 \leq 3。
证明
假设现在给出任意一个正整数 k,考察下式:
- 对于 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。
1 \sim n 中的 f 函数值显然可以线性筛筛出来,由于其完全异或性,可以递推出 f(i!) 的值。
记 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)。
#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;
}