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
#include <iostream>
#include <map>
#include <vector>
#include <set>
using namespace std;

int n;
map<int, int> m;

bool t[300010];
vector<int> v;

void fill(int *&tab, int a) {
        tab[1] += a;

        set<int> s;
        s.clear();
        for(const auto &x : v) {
                for(int i=x;i<=n;i+=x) {
                        if(a / i == 0)
                                break;
                        if(!s.empty() && s.find(i) != s.end())
                                continue;
                        tab[i] += (a / i) * i;
                        //cout << tab[i] << " " << (a / i) * i << " " << a << " " << i << endl;
                        s.insert(i);
                }
        }
}

void solve(int *&tab) {
        for(const auto &pair : m)
                fill(tab, pair.second);
}

int main() {
        ios_base::sync_with_stdio(NULL);
        cout.tie(nullptr);
        cin.tie(nullptr);

        cin >> n;

        for(int i=2;i<=n;++i) {
                if(!t[i]) {
                        v.push_back(i);
                        for(int j=i+i;j<=n;j+=i)
                                t[j] = true;
                }
        }

        int *tab = new int[n+10]();
        for(int i=0;i<=n+1;++i)
                tab[i] = 0;

        for(int i=0;i<n;++i) {
                int a;
                cin >> a;
                ++m[a];
        }

        solve(tab);

        for(int i=1;i<=n;++i)
                cout << tab[i] << " ";

        delete[] tab;
        tab = nullptr;

        return 0;
}