C - Coprime Set Editorial by evima


The problem is basically harder for larger \(N\), so let us think of a way to make \(N\) larger.


◆Basic Strategy

If a set \(A = \{a_1,\ldots,a_n\}\) satisfies the conditions, it will still satisfy them after we add a multiple of \(a_i\) to it.

For example, let us start with Sample Output 1: \(A = \{84, 60, 105, 70\}\). We can add multiples of \(84\) and multiples of \(60\) while still satisfying the conditions. After making as many additions as possible, we can achieve \(N = 429\): the set of all numbers that are multiples of \(84\), \(60\), \(105\), or \(70\).


◆Our Solutions

Starting with \(A = \{84,60,105,70\}\) achieved \(N = 429\). We can make a better choice of \(A\) at the beginning to achieve larger \(N\).

  • Writer’s solution: the set of all numbers that are multiples of \(6\), \(10\), or \(15\) has \(2666\) elements and satisfies the conditions.
  • Tester’s solution: the set of all numbers that are multiples of \(6\), \(10\), \(14\), \(22\), or \(1155\) has \(2926\) elements and satisfies the conditions.

We can solve the problem by printing a coprime subset of such a set.

【Sample Implementation】 https://atcoder.jp/contests/arc118/submissions/22269560 (Python, \(N \leq 2666\)

posted:
last update: