「CF1622F」Quadratic Set

    「CF1622F」Quadratic Set

    CF1622F

    给出一个集合 A={1,2,…,n}={x∈Z∣1≤x≤n}A = \{1, 2, \dots, n\} = \{x \in \mathbb{Z} \mid 1 \leq x \leq n\}。

    你需要寻找一个非空集合 A′⊆AA' \subseteq A,使得 ∏k∈A′k!\prod_{k \in A'} k! 是一个完全平方数。 在此基础上,你需要最大化 ∣A′∣|A'|,并以任意顺序给出集合 A′A' 中的所有数。

    数据范围:1≤n≤1061 \leq n \leq 10^6。

    时空限制:44s / 256256MiB。

    Solution

    结论

    至少存在一个方案,使得集合 AA 中不选的数的个数 ≤3\leq 3。

    证明

    假设现在给出任意一个正整数 kk,考察下式:

    ∏i=12ki!=∏i=1k(2i−1)!⋅(2i)!=∏i=1k((2i−1)!)2⋅2i=(∏i=1k(2i−1)!)2⋅2k⋅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≡0(mod4)n \equiv 0 \pmod 4,可以取 A′=A∖{n2}A' = A \setminus \left\{ \frac{n}{2} \right\}。
    • 对于 n≡2(mod4)n \equiv 2 \pmod 4,可以取 A′=A∖{2,n2}A' = A \setminus \left\{2, \frac{n}{2}\right\}。
    • 对于 n≡1(mod2)n \equiv 1 \pmod 2,可以先不取 nn 这个数,然后转换为上述两种情况之一。

    Q.E.D.


    现在有了很优秀的构造解,但注意到该解不一定是最优解,还要处理集合 AA 中不选的数恰好为 0,1,20, 1, 2 时的解。

    考虑完全平方数的本质:在唯一分解形式下,所有质因子的次数均为偶数。这时候就可以考虑使用 xor hashing。

    定义完全异或性哈希函数 f(x)f(x),一开始先给 1∼n1 \sim n 中的所有质数 pp 的 f(p)f(p) 赋一个范围较大的随机数,其他的合数的 f(x)f(x) 定义为 xx 所有质因子的 ff 函数的异或和(多个相同质因子需要重复异或),特别地 f(1)=0f(1) = 0。在这样的定义下,xx 为完全平方数当且仅当 f(x)=0f(x) = 0。

    1∼n1 \sim n 中的 ff 函数值显然可以线性筛筛出来,由于其完全异或性,可以递推出 f(i!)f(i!) 的值。

    记 P=f(1!)⨁f(2!)⨁⋯⨁f(n!)P = f(1!) \bigoplus f(2!) \bigoplus \cdots \bigoplus f(n!)。

    • 对于所有都选的情况,判断 PP 是否为 00 即可。
    • 对于不选 11 个数的情况,相当于判断是否存在一个 ii 使得 P⨁f(i!)=0P \bigoplus f(i!) = 0,枚举即可。
    • 对于不选 22 个数的情况,相当于判断是否存在一对 i,ji,j 使得 P⨁f(i!)⨁f(j!)=0P \bigoplus f(i!) \bigoplus f(j!) = 0,可以先将所有 f(j!)f(j!) 的值存入一个哈希表或 std::map,再在这个容器中查找 P⨁f(i!)P \bigoplus f(i!) 即可。

    实现的较好可以做到 O(n)\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;
    }