Quadratic Set (Codeforces 1622F)
Tags: Math, hashing

Let's call a set of positive integers $$$a_1, a_2, \dots, a_k$$$ quadratic if the product of the factorials of its elements is a square of an integer, i. e. $$$\prod\limits_{i=1}^{k} a_i! = m^2$$$, for some integer $$$m$$$.You are given a positive integer $$$n$$$.Your task is to find a quadratic subset of a set $$$1, 2, \dots, n$$$ of maximum size. If there are multiple answers, print any of them.

Input: A single line contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$).

Output: In the first line, print a single integer — the size of the maximum subset. In the second line, print the subset itself in an arbitrary order.


Sample Inputs:
1

4

7

9

Sample Outputs:
1
1

3
1 3 4

4
1 4 5 6

7
1 2 4 5 6 7 9

Solution (Python):
""""""
import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
output = sys.stdout.write
DEBUG = os.environ.get('debug') is not None
if DEBUG:
    from inspect import currentframe, getframeinfo
    from re import search

def debug(*args):
    if not DEBUG:
        return
    frame = currentframe().f_back
    s = getframeinfo(frame).code_context[0]
    r = search('\\((.*)\\)', s).group(1)
    vnames = r.split(', ')
    var_and_vals = [f'{var}={val}' for (var, val) in zip(vnames, args)]
    prefix = f'{currentframe().f_back.f_lineno:02d}: '
    print(f"{prefix}{', '.join(var_and_vals)}")
INF = float('inf')

def batch_xor_hash(N):
    """"""
    import random
    random.seed(123)
    MAX = (1 << 64) - 1
    pmap = {}
    hash = [0] * (N + 1)
    mpf = [0] * (N + 1)
    for i in range(2, N + 1):
        if mpf[i] == 0:
            pmap[i] = random.randint(0, MAX)
            hash[i] ^= pmap[i]
            mpf[i] = i
        for (p, h) in pmap.items():
            if p > mpf[i] or p * i > N:
                break
            mpf[p * i] = p
            hash[p * i] ^= hash[i] ^ h
    return (hash, pmap)

def solve(N):
    if N <= 3:
        return [1]
    (hash, _) = batch_xor_hash(N)
    xor = hf = 0
    lookup = {}
    for n in range(2, N + 1):
        hf ^= hash[n]
        xor ^= hf
        lookup[hf] = n
    if xor == 0:
        return list(range(1, N + 1))
    if xor in lookup:
        n = lookup[xor]
        debug(xor, n)
        return [i for i in range(1, N + 1) if i != n]
    for (h1, n1) in lookup.items():
        h2 = xor ^ h1
        if h2 in lookup:
            n2 = lookup[h2]
            return [i for i in range(1, N + 1) if i != n1 and i != n2]
    return [i for i in range(1, N) if i != 2 and i != N // 2]

def main():
    N = int(input())
    out = solve(N)
    print(len(out))
    print(*out)
if __name__ == '__main__':
    main()

Solution (Python):
import random
import time
n = int(input())
n += 1
era = [0] * n
primes = []
for i in range(2, n):
    if era[i] == 0:
        primes.append(i)
        k = i
        while k < n:
            if era[k] == 0:
                era[k] = i
            k += i
hashes = {}
prime = {}
for guy in primes:
    r = random.randrange(0, 1 << 48)
    while r in prime:
        r = random.randrange(0, 1 << 48)
    hashes[guy] = r
    prime[r] = guy
hashall = [0, 0]
for i in range(2, n):
    xor = 0
    k = i
    while k > 1:
        p = era[k]
        i = 0
        while p == era[k]:
            k //= p
            i += 1
        if i % 2 == 1:
            xor ^= hashes[p]
    hashall.append(xor)
hashfac = [0, 0]
for i in range(2, n):
    hashfac.append(hashfac[-1] ^ hashall[i])
facmap = {}
for i in range(1, n):
    facmap[hashfac[i]] = i
total = 0
for i in range(1, n):
    total ^= hashfac[i]
if total == 0:
    print(n - 1)
    print(*[i for i in range(1, n)])
elif total in facmap:
    k = facmap[total]
    size = n - 2
    print(size)
    print(*[i for i in range(1, n) if i != k])
else:
    for i in range(1, n):
        x = total ^ hashfac[i]
        if x in facmap:
            j = facmap[x]
            print(n - 3)
            print(*[l for l in range(1, n) if l != i and l != j])
            break
    else:
        print(n - 4)
        print(*[i for i in range(1, n) if i != 2 and i != n - 1 and (i != (n - 2) // 2)])

Solution (Python):
import sys
import collections
import random
infile = sys.stdin.buffer

def gs():
    return infile.readline().rstrip()

def gi():
    return int(gs())

def gss():
    return gs().split()

def gis():
    return [int(x) for x in gss()]
MOD = 998244353
N = gi()
p = list(range(0, N + 1))
hhh = [-1] * (N + 1)

def hash_(e):
    if hhh[e] == -1:
        hhh[e] = random.getrandbits(48)
    return hhh[e]
for i in range(2, N + 1):
    if p[i] == i:
        j = 2 * i
        while j <= N:
            p[j] = min(p[j], i)
            j += i
c = 0
fact = [0] * (N + 1)
pre = [0] * (N + 1)
fact[1] = c
pre[1] = c
seen = {c: 1}
i = 2
while i <= N:
    c = i
    fact[i] ^= fact[i - 1]
    while c != 1:
        fact[i] ^= hash_(p[c])
        c //= p[c]
    seen[fact[i]] = i
    pre[i] ^= pre[i - 1]
    pre[i] ^= fact[i]
    i += 1

def output(forbidden, n):
    i = 1
    last = n
    if last in forbidden:
        last -= 1
    if last in forbidden:
        last -= 1
    while i <= n:
        if i not in forbidden:
            sys.stdout.write(str(i))
            if i < last:
                sys.stdout.write(' ')
        i += 1
    sys.stdout.flush()

def f(n):
    if n == 1:
        print(1)
        print(1)
        return
    if pre[n] == 0:
        print(n)
        print(' '.join(map(str, range(1, n + 1))))
        return
    i = 2
    while i <= n:
        if pre[n] ^ fact[i] == 0:
            forbidden = set([i])
            print(n - len(forbidden))
            output(forbidden, n)
            return
        i += 1
    i = 2
    while i <= n:
        if pre[n] ^ fact[i] in seen:
            j = seen[pre[n] ^ fact[i]]
            forbidden = set([i, j])
            forbidden = set([e for e in forbidden if e != 1])
            print(n - len(forbidden))
            output(forbidden, n)
            return
        i += 1
    forbidden = set([2, n // 2, n])
    print(n - len(forbidden))
    output(forbidden, n)
    return

def main(infn=''):
    global infile
    infile = open(infn, 'r') if infn else open(sys.argv[1], 'r') if len(sys.argv) > 1 else sys.stdin
    cs = 1
    for case in range(1, cs + 1):
        f(N)
if __name__ == '__main__':
    main()