解答：Submission #10499621 - AtCoder Grand Contest 022
解法：解説AC。
aiの和をSとすると、gcd(ai, S) > 1 でgcd(a1, a2, ..., an) = 1を満たすaiの構築をすればよい。
制約がN ≦ 20000、ai ≦ 30000であり、N = 20000の時は30000から2/3程度選ばれていることになる。
ここで「Sが6の倍数であり、aiが2の倍数または3の倍数でかつ2と3を含む」とすると、このaiは問題の条件をクリアしている。これはaiを6k+2, 6k+3, 6k+4, 6kと選んでいき、最後にこの数列を修正してあげることで達成できる。
Sの和の推移は、mod 6で2, 5, 3, 3, 5, 2, 0, 0 であり（次は2に戻って繰り返す）、修正すべき場合はS≡2, 3, 5(mod 6)の場合である。なお、aiが上限の30000をとるときはS≡0(mod 6)である。（上記の8項の最後の0）
修正方法は下記の通り。
- S≡2(mod 6)の場合：8を除去して30000を追加する。(30000は必ず使われていない)
- S≡3(mod 6)の場合：9を除去して30000を追加する。(30000は必ず使われていない)
- S≡5(mod 6)の場合：9を除去して29998を追加する。(29998は必ず使われていない)
