1038B.md (1517B)
1 Source: https://codeforces.com/problemset/problem/1038/B 2 3 B. Non-Coprime Partition 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Find out if it is possible to partition the first $n$ positive integers into two non-empty disjoint sets $S_1$ and $S_2$ such that: 22 23 $\mathrm{gcd}(\mathrm{sum}(S_1), \mathrm{sum}(S_2)) \gt 1$ 24 25 Here $\mathrm{sum}(S)$ denotes the sum of all elements present in set $S$ and $\mathrm{gcd}$ means the[greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor). 26 27 Every integer number from $1$ to $n$ should be present in exactly one of $S_1$ or $S_2$. 28 29 Input 30 31 The only line of the input contains a single integer $n$ ($1 \le n \le 45\,000$) 32 33 Output 34 35 If such partition doesn't exist, print "No" (quotes for clarity). 36 37 Otherwise, print "Yes" (quotes for clarity), followed by two lines, describing $S_1$ and $S_2$ respectively. 38 39 Each set description starts with the set size, followed by the elements of the set in any order. Each set must be non-empty. 40 41 If there are multiple possible partitions — print any of them. 42 43 Examples 44 45 Input 46 47 ``` 48 1 49 ``` 50 51 Output 52 53 ``` 54 No 55 ``` 56 57 Input 58 59 ``` 60 3 61 ``` 62 63 Output 64 65 ``` 66 Yes 67 1 2 68 2 1 3 69 ``` 70 71 Note 72 73 In the first example, there is no way to partition a single number into two non-empty sets, hence the answer is "No". 74 75 In the second example, the sums of the sets are $2$ and $4$ respectively. The $\mathrm{gcd}(2, 4) = 2 \gt 1$, hence that is one of the possible answers.