Ограничение по времени: 1 секунда Ограничение по п...

Идея довольно красивая. Сожмём массив по значениям: пусть cnt[x] — сколько раз встречается x, а D — число различных значений.

Если мы хотим полностью убрать значение x из массива, нужно изменить все cnt[x] его вхождений. Значит, «стоимость удаления значения x» равна cnt[x].

При этом изменённое x можно превратить в любое кратное x.

1. Какие значения можно убрать без появления нового значения?

Если в итоговом массиве остаётся значение y, то любое x | y можно целиком превратить в y.

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

$$x\mid y.$$

Назовём значение максимальным, если среди присутствующих значений нет другого его кратного.

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

text
1 2 3 4

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

Причём важный факт:

Если оставить все максимальные значения, то любое немаксимальное значение можно удалить независимо от остальных.

Почему? Если x немаксимально, существует большее присутствующее кратное. Поднимаясь по кратным, рано или поздно придём к максимальному значению y, причём x | y.

Таким образом, среди немаксимальных значений мы просто хотим удалить как можно больше значений при бюджете k. Стоимость удаления x — cnt[x].

Значит, нужно взять самые маленькие cnt[x].

---

2. А можно ли удалить максимальное значение?

Да, но тогда его уже некуда превратить среди оставшихся исходных значений.

Однако все такие «проблемные» изменённые значения можно собрать в одно новое значение — например, в их НОК (конкретно считать НОК не нужно).

Если мы полностью удалили t различных исходных значений, но среди них есть хотя бы одно максимальное, то эти t значений заменятся минимум одним новым.

То есть число различных уменьшается не на t, а на

$$t-1.$$

Следовательно, есть два варианта.

• Удаляем только немаксимальные значения. Если можем удалить t штук, выигрыш = t.
• Удаляем произвольные значения. Если можем удалить t самых дешёвых вообще, выигрыш = t-1.

Ответ:

$$D-\max(t_{\text{nonmax}},\ t_{\text{all}}-1).$$

Для t_all = 0 считаем второй выигрыш равным 0.

---

Как найти максимальные значения

Есть present[x].

Для каждого присутствующего x проверяем его кратные:

cpp
for (int y = 2*x; y <= MAX; y += x)
    if (present[y])
        x is non-maximal;

Суммарная сложность:

$$\sum_{x=1}^{M} \frac Mx=O(M\log M),$$

где M <= 10^6, это нормально.

После этого собираем два массива стоимостей:

text
all       = cnt[x] для всех различных x
nonmax    = cnt[x] только для немаксимальных x

сортируем их и строим префиксные суммы.

Для каждого k ищем максимальное число элементов, чей префикс <= k.

---

На примере:

text
3 4 1 2 1 2

частоты:

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

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

Немаксимальные: 1, 2, их стоимости:

text
[2, 2]

Все стоимости:

text
[1, 1, 2, 2]

Например, при k=2 можно удалить два значения с частотой 1, то есть 3 и 4, но они сольются в одно новое значение: выигрыш 2-1=1, ответ 4-1=3.

При k=4 можно удалить 1 и 2, превратив их, например, в 4: выигрыш 2, ответ 2.

Получаем:

text
4 4 3 3 2 2 1

Итоговая сложность — примерно O(M log M + n log n), память O(M+n).

Поиск максимальных по делимости работает так:

cpp
for (int x = 1; x <= M; x++) {
  if (!cnt[x]) continue;
  for (int y = x + x; y <= M; y += x) {
    if (cnt[y]) {
      // x не максимальный
    }
  }
}

Для фиксированного x мы перебираем

$$2x,3x,\ldots,\left\lfloor\frac Mx\right\rfloor x,$$

то есть не более

$$\frac Mx$$

чисел.

Поэтому общее количество итераций не больше

$$\sum_{x=1}^{M}\frac Mx = M\sum_{x=1}^{M}\frac1x.$$

А гармоническая сумма

$$1+\frac12+\frac13+\ldots+\frac1M = O(\log M).$$

Например, это можно увидеть группировкой:

$$1+ \left(\frac12\right)+ \left(\frac13+\frac14\right)+ \left(\frac15+\ldots+\frac18\right)+\ldots$$

В каждой группе максимум 1, а групп всего O(log M).

Значит,

$$\sum_{x=1}^{M}\frac Mx=O(M\log M).$$

Причём у нас цикл запускается только для присутствующих x, так что фактически итераций даже меньше.

Код в твоём стиле, только solve:

cpp
void solve() {
  int n;
  cin >> n;

  vector< int > a(n);
  int mx = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    mx = max(mx, a[i]);
  }

  vector< int > cnt(mx + 1);
  for (int x : a) {
    cnt[x]++;
  }

  int dif = 0;
  for (int x = 1; x <= mx; x++) {
    if (cnt[x]) dif++;
  }

  vector< bool > bad(mx + 1);

  for (int x = 1; x <= mx; x++) {
    if (!cnt[x]) continue;

    for (int y = x + x; y <= mx; y += x) {
      if (cnt[y]) {
        bad[x] = 1;
        break;
      }
    }
  }

  vector< int > all;
  vector< int > nonmax;

  for (int x = 1; x <= mx; x++) {
    if (!cnt[x]) continue;

    all.push_back(cnt[x]);
    if (bad[x]) {
      nonmax.push_back(cnt[x]);
    }
  }

  sort(all.begin(), all.end());
  sort(nonmax.begin(), nonmax.end());

  vector< int > pa(all.size() + 1);
  vector< int > pn(nonmax.size() + 1);

  for (int i = 0; i < all.size(); i++) {
    pa[i + 1] = pa[i] + all[i];
  }

  for (int i = 0; i < nonmax.size(); i++) {
    pn[i + 1] = pn[i] + nonmax[i];
  }

  for (int k = 0; k <= n; k++) {
    int x = upper_bound(pn.begin(), pn.end(), k) - pn.begin() - 1;
    int y = upper_bound(pa.begin(), pa.end(), k) - pa.begin() - 1;

    int del = x;
    if (y) {
      del = max(del, y - 1);
    }

    cout << dif - del << " ";
  }
  cout << "\n";
}

Ещё один момент: break внутри поиска кратного не портит оценку — он только уменьшает число итераций, поэтому верхняя граница всё равно O(M log M).