Peculiar Partitioning

Peculiar Partitioning

Limits 1s, 1.0 GB

You are given an array aaa of length nnn. You need to find a sub-sequence SSS of the array such that gcd(sum(S),sum(S‾))>1.gcd(sum(S), sum(\overline S) )> 1.gcd(sum(S),sum(S))>1. In other words, the gcd of sum of elements in SSS and sum of elements not in SSS is greater than 1. It is also required that both SSS and S‾\overline SS are non-empty.


This is a companion discussion topic for the original entry at https://toph.co/p/primordial-partitioning