CF1038B Non-Coprime Partition

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: $ \mathrm{gcd}(\mathrm{sum}(S_1), \mathrm{sum}(S_2)) > 1 $ 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). Every integer number from $ 1 $ to $ n $ should be present in exactly one of $ S_1 $ or $ S_2 $ .

N/A

N/A

In the first example, there is no way to partition a single number into two non-empty sets, hence the answer is "No". In the second example, the sums of the sets are $ 2 $ and $ 4 $ respectively. The $ \mathrm{gcd}(2, 4) = 2 > 1 $ , hence that is one of the possible answers.