309091: CF1622F. Quadratic Set
Memory Limit:256 MB
Time Limit:4 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Quadratic Set
题意翻译
给你 $n$ 个数 $1,2,3,\cdots,n$,构成一个集合 $A$。 称一个集合 $S$ 为**平方集合**,当且仅当 $\prod\limits_{k\in S}k!$ 是一个完全平方数。 你需要找到一个最大的集合 $A'\subseteq A$,满足 $A'$ 是一个**平方集合**。 请你求出 $A'$ 的大小以及 $A'$ 中的所有元素,注意 $A'$ 中的元素可以按照任意顺序输出。 $1\le n\le 10^6$题目描述
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.输入输出格式
输入格式
A single line contains a single integer $ n $ ( $ 1 \le n \le 10^6 $ ).
输出格式
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.
输入输出样例
输入样例 #1
1
输出样例 #1
1
1
输入样例 #2
4
输出样例 #2
3
1 3 4
输入样例 #3
7
输出样例 #3
4
1 4 5 6
输入样例 #4
9
输出样例 #4
7
1 2 4 5 6 7 9