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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;


int main(int argc, char* argv[])
{
#ifdef _DEBUG
	freopen("input.txt", "rt", stdin);
#endif
	int n;
	scanf("%d", &n);
	vi res(n + 1, 0);
	map<int, int> val2num;
	for (int i = 0; i < n; i++) {
		int v;
		scanf("%d", &v);
		val2num[v]++;
	}
	map<int, int> num2repeats;
	for (auto p : val2num)
		num2repeats[p.second]++;
	vector<pii> data(num2repeats.rbegin(), num2repeats.rend());
	data.push_back(pii(-1, 0)); // barrier to simplify loop condition for(j...)
	for (int k = 1; k <= data[0].first; k++) {
		for (int j = 0; data[j].first >= k; j++) {
			res[k] += (k * (data[j].first / k)) * data[j].second;
#ifdef _DEBUG
			fprintf(stderr, "k=%d, j=%d, p=(%d,%d)\t", k, j, data[j].first, data[j].second);
			fprintf(stderr, "%d\t%d\t%d\t%d\n",
				data[j].first / k,
				(k * (data[j].first / k)),
				(k * (data[j].first / k)) * data[j].second,
				res[k]
				);
#endif
		}
	}
	printf("%d", res[1]);
	for (int k = 2; k <= n; k++)
		printf(" %d", res[k]);
	printf("\n");

	return 0;
}