Contest Duration: - (local time) (120 minutes) Back to Home

## 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: