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
/* 2024
 * Maciej Szeptuch
 */
#include <algorithm>
#include <cstdio>

const int MAX_STAMPS = 300001;

int cities;
int count[MAX_STAMPS];
int sizes;
int stamp[MAX_STAMPS];
int stamps;
int result[MAX_STAMPS];

int main(void)
{
    scanf("%d", &stamps);
    for(int s = 0; s < stamps; ++s)
        scanf("%d", &stamp[s]);

    std::sort(stamp, stamp + stamps);
    for(int s = 0; s < stamps; ++s)
    {
        int e = s + 1;
        while(e < stamps && stamp[e] == stamp[s])
            ++e;

        stamp[cities++] = e - s;
        s = e - 1;
    }

    std::sort(stamp, stamp + cities);
    for(int s = 0; s < cities; ++s)
    {
        int e = s + 1;
        while(e < cities && stamp[e] == stamp[s])
            ++e;

        count[sizes] = e - s;
        stamp[sizes++] = stamp[s];
        s = e - 1;
    }

    for(int b = stamp[sizes - 1]; b > 0; --b)
    {
        for(int s = sizes - 1; s >= 0 && stamp[s] >= b; --s)
            result[b - 1] += count[s] * (stamp[s] - (stamp[s] % b));
    }

    for(int s = 0; s < stamps; ++s)
        printf("%d ", result[s]);

    puts("");

    return 0;
}