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: