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
#include <iostream>
#include <unordered_map>
#include <bits/stdc++.h>
#include <algorithm>

using namespace std;

int main(int argc, char const *argv[])
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    int sum = 0;

    std::cin >> n;
    sum += n;

    std::unordered_map<long, long> frequency;

    for (int i = 0; i < n; i++) {
        long num;
        std::cin >> num;
        if (frequency.find(num) == frequency.end()) 
        {
            frequency.insert(std::make_pair(num, 1));
        }
        // Else update the frequency
        else
        {
            frequency[num]++;
        }
    }

    std::vector<std::pair<int, int>> frequency_vector(frequency.begin(), frequency.end());

    // Sort the frequency vector by value
    std::sort(frequency_vector.begin(), frequency_vector.end(), [](const std::pair<int, int>& p1, const std::pair<int, int>& p2) {
        return p1.second < p2.second;
    });

    // Print the sorted frequency map
    // for (const auto& pair : frequency_vector) {
    //     std::cout << pair.first << ": " << pair.second << std::endl;
    // }

    cout << sum;

    for (int i = 2; i <= n; i++) {
        int local_sum = 0;
        int j = 1;
        while (true) {
            int val1 = i * j;
            // Find index of first position in frequency_vector where frequency value is greatet equal than val
            auto it = lower_bound(frequency_vector.begin(), frequency_vector.end(), val1, [](const std::pair<int, int>& p, int val) {
                return p.second < val;
            });
            if (it - frequency_vector.begin() > frequency_vector.size() - 1 ||
                (it - frequency_vector.begin() == frequency_vector.size() - 1 && val1 > frequency_vector[frequency_vector.size() - 1].second)) {
                break;
            }
            // Print found index
            //cout << "Index: " << it - frequency_vector.end() << std::endl;
            //cout << i << " " << j << " " << it - frequency_vector.begin() << endl;
            local_sum += i * (frequency_vector.size() - (it - frequency_vector.begin()));
            j++;
        }
        //cout << "Local sum: " << local_sum << std::endl;
        cout << " " << local_sum;
    }

    return 0;
}