轻拍牛头

LibreOJ-10199-轻拍牛头

实现

// 92/100
#include <iostream>
using namespace std;

const int N = 100010, M = 1000010;
int n, a[N];
int res[M];

int main () {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);

    int b = 0;
    for (int i = 1; i <= n; ++ i) b = max(b, a[i]);
    for (int i = 1; i <= n; ++ i)
        for (int j = a[i]; j <= b; j += a[i])
            ++ res[j];

    for (int i = 1; i <= n; ++ i)
        printf("%d\n", res[a[i]] - 1);
    return 0;
}

// 100/100
#include <iostream>
using namespace std;

const int N = 100010, M = 1000010;
int n, a[N];
int cnt[M], res[M];

int main () {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);

    for (int i = 1; i <= n; ++ i) ++ cnt[a[i]];
    for (int i = 1; i < M; ++ i)
        for (int j = i; j < M; j += i)
            res[j] += cnt[i];
    
    for (int i = 1; i <= n; ++ i)
        printf("%d\n", res[a[i]] - 1);
    return 0;
}

// 100/100
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100010, M = 1000010;
int n, m, a[N], b, c[N];
int cnt[M], res[M];

int main () {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);

    for (int i = 1; i <= n; ++ i) b = max(b, a[i]);
    for (int i = 1; i <= n; ++ i) c[i] = a[i];
    for (int i = 1; i <= n; ++ i) ++ cnt[a[i]];
    sort(a + 1, a + n + 1);
    m = unique(a + 1, a + n + 1) - (a + 1);
    
    for (int i = 1; i <= m; ++ i)
        for (int j = a[i]; j <= b; j += a[i])
            res[j] += cnt[a[i]];
    
    for (int i = 1; i <= n; ++ i)
        printf("%d\n", res[c[i]] - 1);
    return 0;
}