Когда Пеннивайз решил испугать Эдди, он даже немно...

Идея довольно красивая: задача сводится к частотам различных значений и максимальным элементам по делимости.

Пусть какое-то значение x встречается cnt[x] раз. Чтобы значение x полностью исчезло из массива, нужно изменить все cnt[x] его копий. Поэтому удобно считать, какие исходные значения мы вообще оставляем неизменными.

Если мы оставили значения b1, ..., bt, то все остальные элементы, которые делят хотя бы одно из bi, можно домножить до этого bi.

Теперь рассмотрим максимальные по делимости значения: x такое, что в исходном массиве нет другого значения y != x, для которого x | y.

Например, для

text
1 2 3 4

максимальные — 3 и 4.

Важное наблюдение: если мы хотим получить итоговые значения, которые все уже присутствовали в исходном массиве, то обязаны оставить все максимальные значения. Максимальное x невозможно превратить в другое оставленное исходное значение, потому что оно не делит никакое другое.

И наоборот: если оставить все максимальные значения, то каждое немаксимальное значение делит какое-нибудь максимальное (можно просто идти вверх по цепочке делимости).

---

Пусть различных значений всего m, а максимальных — M.

Хотим получить ровно d различных значений.

Есть два варианта.

1. Все итоговые значения взяты из исходного массива.

Тогда обязательно оставляем все M максимальных. Если d > M, дополнительно можем оставить любые d-M немаксимальных значений.

Чтобы потратить минимум ходов, естественно оставить те, у которых самые большие частоты.

Если

text
Smax = сумма cnt[x] по максимальным x

и частоты немаксимальных отсортированы по убыванию, то

text
cost1[d] =
    n - Smax - сумма (d-M) наибольших частот немаксимальных

для d >= M.

---

2. Создаём одно новое значение.

Это ещё один важный трюк.

Можно взять любые несколько разных чисел и все их копии домножить до их общего кратного, например до НОК. Поэтому все значения, которые мы решили не оставлять, можно слить в одно новое значение.

Если итоговых различных значений должно быть d, то можем оставить d-1 исходных значений, а всё остальное слить в одно новое.

Тогда выгодно оставить просто d-1 самых частых исходных значений:

text
cost2[d] =
    n - сумма (d-1) наибольших частот среди всех значений.

В частности,

text
cost2[1] = n

— меняем вообще все элементы и отправляем их в общий НОК.

Итого:

text
cost[d] = min(cost1[d], cost2[d])

где cost1 существует только при d >= M.

cost[d] — минимальное число ходов, за которое можно получить d различных значений.

После этого для каждого k нужен минимальный d, для которого

text
cost[d] <= k.

Почему <=, а не =? Лишний ход можно потратить, умножив какой-нибудь элемент на 1 (натуральное число).

---

Для примера

text
3 4 1 2 1 2

частоты:

text
1 -> 2
2 -> 2
3 -> 1
4 -> 1

Максимальные по делимости: 3, 4.

Получаем:

text
d=4: cost = 0
d=3: cost = 2
d=2: cost = 4
d=1: cost = 6

Значит ответы для k=0..6:

text
4 4 3 3 2 2 1

как в примере.

Максимальные значения можно найти решетом: для каждого присутствующего x проверить, есть ли среди 2x,3x,... присутствующее число. При ai <= 1e6 суммарно это порядка A log A, то есть нормально.

Итого сложность примерно O(A log A + n log n), где A = 10^6.