By Lindsey L. (11th Grade)
https://codeforces.com/contest/2173/problem/C 12/13/25
Concepts: greedy, number theory
Observations
- Must always include the first number in b
- If there are less than k / x multiples of x in the array, it is impossible
Solution:
sort the array and store it in a set. Use a map to keep track of which elements already have a divisor in b. Loop through the array and add the smallest unused element to b, then check all its multiples. If one of them doesn’t exist, it is impossible, otherwise it should be marked as used.
