AGC022 B GCD Sequence - tarattataのブログ

問題の概要

Nが与えられたとき、サイズN、各要素が30000以下の、以下のような数列を１つ求めよ。
- 全ての要素は相異なる
- 全ての要素の $gcd$ が1
- 全要素の和を $S$ とするとき、全ての i に対して $gcd(a_{i}, S-a_{i}) ≠ 1$

制約

$3 \le N \le 20000$

解法

まず最初に、 $gcd(a_{i}, S-a_{i}) ≠ 1$ という条件は $gcd(a_{i}, S) ≠ 1$ と書き換えてよいことがわかります。

gcdが1という条件については、2と3を必ず選んでおけば達成できるので、あとは残りの要素を2の倍数や3の倍数から選んで、和 Sを6の倍数にできれば達成できます。
30000以下の正整数30000個の中から最大20000個を選ぶというのは、かなり個数が多いですが、「2の倍数または3の倍数」は 1以上30000以下の整数のうち 20000個あるので、わりと達成できそうです。
難しかったら5の倍数も入れて、Sを30の倍数にすればよさそう。

ただ、この解法だと、細部をつめて実装するのが、そこそこ大変そうです。

考え続けていたら、以下の解が思い浮かびました。

数列の要素として、以下のように2個ずつのペアを選ぶ。
$「x」と「30000-x」（ただしxは15000未満で、15000と互いに素でない正整数）$
$N$ が偶数なら、このようなペアを選んで要素数が $N$ になったら終了。
$N$ が奇数なら、このようなペアを選んで要素数を $N-1$ にした後、「15000」を要素として追加。

こうすれば、和が15000の倍数になり、条件を満たします。

解答例

https://atcoder.jp/contests/agc022/submissions/10973698