Solution -「CF 1622F」Quadratic Set
\(\mathscr{Description}\)
??Link.
??求 \(S\subseteq\{1,2,\dots,n\}\),使得 \(\prod_{i\in S}i\) 是完全平方数,并最大化 \(|S|\)。
??\(n\le10^6\)。
\(\mathscr{Solution}\)
??爆搜打出 \(20\) 以内的表,发现 \(|S|\approx n\)。先研究偶数 \(n=2k\):
\[\begin{aligned} \prod_{i=1}^{2k} i! &= \left( \prod_{i=1}^k i! \right)^2 \prod_{i=1}^k 2i\\ &= \left( \prod_{i=1}^k i! \right)^2 2^k k!. \end{aligned} \]那么若 \(2^kk!\) 是完全平方数,有 \(|S|=n\);否则若 \(2^k\) 是完全平方数,有 \(|S|=n-1\),删去 \(k!\) 即可;否则至少有 \(|S|=n-2\),只需要删去 \(2!\) 和 \(k!\)。继而,对于奇数 \(n=2k+1\),答案至少为 \(n-3\)。
??所以,我们只需要判断 \(|S|\) 能否取 \(n,n-1,n-2\)。这里有个 trick:异或哈希。对于每个素数 \(p\),独立随机生成 hash 值 \(h(p)\),并定义 \(h(ab)=h(a)\oplus h(b)\),这样就能对每个数建立 hash,若两数 \(x,y\) 的唯一分解中指数奇偶性完全一致,就应有 \(h(x)=h(y)\)。利用这个 trick,求出所有 \(h(i!)\) 后顶多拿 unordered map 判一判就能完成 \(S\) 的取值判断了。复杂度为 \(\mathcal O(n)\)(假定 std::unordered_map
为 \(\mathcal O(1)\) 操作)。
\(\mathscr{Code}\)?
/*+Rainybunny+*/
#include
#define rep(i, l, r) for (int i = l, rep##i = r; i <= rep##i; ++i)
#define per(i, r, l) for (int i = r, per##i = l; i >= per##i; --i)
typedef unsigned long long ULL;
const int MAXN = 1e6;
int n, pn, pr[MAXN + 5];
bool npr[MAXN + 5];
ULL hnum[MAXN + 5], hfac[MAXN + 5];
std::unordered_map buc;
inline void init() {
std::mt19937_64 emt(time(0) ^ 20120712);
rep (i, 2, n) {
if (!npr[i]) hnum[pr[++pn] = i] = emt();
for (int j = 1, t; j <= pn && (t = i * pr[j]) <= n; ++j) {
npr[t] = true, hnum[t] = hnum[i] ^ hnum[pr[j]];
if (!(i % pr[j])) break;
}
}
rep (i, 1, n) hfac[i] = hfac[i - 1] ^ hnum[i];
}
int main() {
scanf("%d", &n), init();
ULL h = 0;
rep (i, 1, n) h ^= hfac[i];
if (!h) {
printf("%d\n", n);
rep (i, 1, n) printf("%d%c", i, i < n ? ' ' : '\n');
return 0;
}
rep (i, 1, n) if (h == hfac[i]) {
printf("%d\n", n - 1);
rep (j, 1, n) if (i != j) printf("%d ", j);
return putchar('\n'), 0;
}
rep (i, 1, n) buc[hfac[i]] = i;
rep (i, 1, n) if (buc.count(h ^ hfac[i])) {
printf("%d\n", n - 2); int tmp = buc[h ^ hfac[i]];
rep (j, 1, n) if (j != i && j != tmp) printf("%d ", j);
return putchar('\n'), 0;
}
printf("%d\n", n - 3);
rep (i, 1, n - 1) if (i != 2 && i != n >> 1) printf("%d ", i);
return putchar('\n'), 0;
}