「Luogu P2926」「USACO08DEC」拍头 Patting Heads

Descripion

给定 $n\ (1 \leq n \leq 10^5)$ 个正整数 $a_i\ (1 \leq a_i \leq 10^6)$ 。对于每一个数 $a_i$，求有多少个数 $j\ (1 \leq j \leq n)$ 满足 $a_i \mid a_j$ 且 $i \neq j$ 。

Source

[Luogu]P2926

Solution

看完题目很容易想到 $O(n^2)$ 的暴力算法，枚举所有 $i$ 和 $j$，显然会超时。但我们发现 $a_i$ 并不大，所以考虑另一种方法。

我们用一个桶 $cnt$ 记录 $a_i$ 出现的次数，$ans_i$ 表示 $a_i=i$ 时的答案，枚举 $i=1 \sim \max \begin{Bmatrix}a_i\end{Bmatrix}$ ，接着枚举 $i$ 以及 $i$ 的倍数，凡是等于 $i$ 或是 $i$ 的倍数的数，答案都应该加上 $i$ 出现的次数。同时因为会把自己算进去，所以答案要减 $1$ 。时间复杂度为 $O(n\log\log n)$，类似 埃拉托斯特尼筛法 。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
	int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 1e5, MAXM = 1e6;
int n, maxn, a[MAXN + 5], cnt[MAXM + 5], ans[MAXM + 5];

int main() {
    read(n);
    for (int i = 1; i <= n; ++i) {
        read(a[i]);
        ++cnt[a[i]];
        maxn = max(maxn, a[i]);
    }
    for (int i = 1; i <= maxn; ++i) {
        if (!cnt[i]) continue;//小优化：判断 i 是否出现过
        for (int j = i; j <= maxn; j += i)//枚举 i 以及 i 的倍数
            ans[j] += cnt[i];//如果 i | j，则让 ans[j] 增加 i 出现的次数
    }
    for (int i = 1; i <= n; ++i) {
        write(ans[a[i]] - 1);//因为 a[i] | a[i]，多算了一次自己，要减 1
        putchar('\n');
    }
    return 0;
}