1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
#include <bits/stdc++.h>
using std::cin, std::cout, std::vector;

void init_io() {
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
}

struct Group {
  unsigned num_cities;
  unsigned num_stamps;
};

vector<unsigned> read_cities() {
  unsigned n;
  cin >> n;
  vector<unsigned> cities;
  cities.reserve(n);
  for (unsigned i=0; i<n; ++i) {
    unsigned city;
    cin >> city;
    cities.push_back(city);
  }
  return cities;
}

vector<Group> calc_groups(vector<unsigned> &cities) {
  std::sort(cities.begin(), cities.end());
  vector<unsigned> num_cities(cities.size() + 1u, 0);
  auto it = cities.begin();
  while (it != cities.end()) {
    auto jt = it + 1;
    while (jt != cities.end() && *jt == *it) ++jt;
    num_cities[jt - it] += 1;
    it = jt;
  }
  vector<Group> groups;
  for (unsigned num_stamps = 1; num_stamps < num_cities.size(); ++num_stamps) {
    const unsigned nc = num_cities[num_stamps];
    if (nc != 0) {
      Group group;
      group.num_cities = nc;
      group.num_stamps = num_stamps;
      groups.push_back(group);
    }
  }
  return groups;
}

vector<unsigned> calc_gifts(const unsigned n, const vector<Group> &groups) {
  vector<unsigned> gift_diffs(n+2, 0);
  const unsigned small_k = static_cast<unsigned>(std::sqrt(n));
  for (unsigned k = 1; k <= small_k; ++k) {
    for (const Group &group : groups) {
      const unsigned gift = group.num_cities * (group.num_stamps / k);
      gift_diffs[k] += gift;
      gift_diffs[k+1] -= gift;
    }
  }

  const unsigned max_v = n / (small_k + 1);
  for (unsigned v = 1; v <= max_v; ++v) {
    for (const Group &group: groups) {
      // floor(group.num_stamps / k) = v
      // group.num_stamps / k >= v
      // group.num_stamps / k < v + 1
      // k <= group.num_stamps / v
      // k > group.num_stamps / (v+1)
      unsigned start_k = group.num_stamps / (v + 1) + 1;
      unsigned end_k = group.num_stamps / v + 1;
      // Note: start_k, end_k <= group.num_stamps + 1 <= n + 1
      start_k = std::max(start_k, small_k+1);
      end_k = std::max(end_k, small_k+1);
      const unsigned gift = group.num_cities * v;
      gift_diffs[start_k] += gift;
      gift_diffs[end_k] -= gift;
    }
  }

  unsigned g = gift_diffs[0];
  vector<unsigned> gifts;
  gifts.reserve(n);
  for (unsigned k = 1; k <= n; ++k) {
    g += gift_diffs[k];
    gifts.push_back(k * g);
  }
  return gifts;
}

void print_gifts(const vector<unsigned> &gifts) {
  for (const unsigned g : gifts) {
    cout << g << " ";
  }
  cout << "\n";
}

int main() {
  init_io();
  vector<unsigned> cities = read_cities();
  const unsigned n = cities.size();
  const vector<Group> groups = calc_groups(cities);
  const vector<unsigned> gifts = calc_gifts(n, groups);
  print_gifts(gifts);
}