1621：轻拍牛头

题目描述

原题来自：USACO 2008 Dec. Silver

今天是贝茜的生日，为了庆祝自己的生日，贝茜邀你来玩一个游戏。

贝茜让 $N$ 头奶牛坐成一个圈。除了 $1$ 号与 $N$ 号奶牛外，$i$ 号奶牛与 $i-1$ 号和 $i+1$ 号奶牛相邻，$N$ 号奶牛与 $1$ 号奶牛相邻。农夫约翰用很多纸条装满了一个桶，每一张包含了一个 $1$ 到 $10^6$ 的数字。

接着每一头奶牛 $i$ 从桶中取出一张纸条 $A_i$，每头奶牛轮流走一圈，同时拍打所有「抽到字条数字是 $A_i$ 的因数」的牛，然后走回到原来的位置。牛们希望你帮助他们确定，每一头奶牛需要拍打的牛。

输入格式

第一行包含一个整数 $N$；

接下来第二到第 $N+1$ 行每行包含一个整数 $A_i$。

输出格式

第一到第 $N$ 行，第 $i$ 行的输出表示第 $i$ 头奶牛要拍打的牛数量。

样例

样例输入 #1

5
2
1
2
3
4

样例输出 #1

2
0
2
1
3

样例解释 #1

• $N=5$ 头奶牛，抽到的数字分别为 $2,1,2,3,4$。
• 奶牛 $1$ 抽到 $2$，需要拍打所有抽到数字是 $2$ 的因数的奶牛。$2$ 的因数为 $1$ 和 $2$，所以抽到 $1$ 或 $2$ 的奶牛都要被拍打。抽到 $1$ 的是奶牛 $2$，抽到 $2$ 的是奶牛 $1$ 和 $3$，但拍打不包括自己（因为自己拍自己？题目说“拍打所有抽到字条数字是 $A_i$ 的因数的牛”，应该包括自己吗？样例中奶牛 $1$ 输出 $2$，说明不包括自己，因为如果包括自己，则奶牛 $1$ 抽到 $2$，因数有 $1$ 和 $2$，抽到 $1$ 的奶牛 $2$，抽到 $2$ 的奶牛 $1$ 和 $3$，共 $3$ 头，但输出是 $2$，说明排除了自己。所以拍打的对象是其他奶牛。
• 因此，奶牛 $1$ 拍打奶牛 $2$（抽到 $1$）和奶牛 $3$（抽到 $2$），共 $2$ 头。
• 奶牛 $2$ 抽到 $1$，$1$ 的因数只有 $1$，所以拍打所有抽到 $1$ 的奶牛（除了自己）。只有奶牛 $2$ 抽到 $1$，所以拍打 $0$ 头。
• 奶牛 $3$ 抽到 $2$，同奶牛 $1$，拍打奶牛 $1$ 和 $2$，共 $2$ 头。
• 奶牛 $4$ 抽到 $3$，$3$ 的因数为 $1$ 和 $3$，拍打抽到 $1$ 的奶牛 $2$ 和抽到 $3$ 的奶牛 $4$（自己排除），所以只拍打奶牛 $2$，共 $1$ 头。
• 奶牛 $5$ 抽到 $4$，$4$ 的因数为 $1,2,4$，拍打抽到 $1$ 的奶牛 $2$，抽到 $2$ 的奶牛 $1$ 和 $3$，抽到 $4$ 的奶牛 $5$（自己排除），所以拍打奶牛 $1,2,3$，共 $3$ 头。

数据范围

对于全部数据，$1 \le N \le 10^5$，$1 \le A_i \le 10^6$。

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：本题需要对于每个 $A_i$，统计有多少个 $A_j$（$j \ne i$）是 $A_i$ 的因数。直接枚举每个数的因数复杂度 $O(N \sqrt{A_i})$ 可能超时。因为 $A_i \le 10^6$，我们可以用桶计数，然后对于每个数字 $x$，枚举 $x$ 的所有倍数 $y$，将 $x$ 的贡献加到 $y$ 上。具体地：

1. 用数组 cnt[x] 记录数字 $x$ 出现的次数。
2. 用数组 ans[x] 记录抽到数字 $x$ 的奶牛需要拍打的牛数量（不包括自己）。
3. 对于每个 $x$，枚举 $x$ 的所有倍数 $y$（$y \le 10^6$），则 $x$ 是 $y$ 的因数，所以抽到 $y$ 的奶牛需要拍打所有抽到 $x$ 的奶牛。因此 ans[y] += cnt[x]。
4. 最后对于每个 $A_i$，输出 ans[A_i] - 1（因为减掉自己）。

时间复杂度：$O(M \log M)$，其中 $M = 10^6$，因为枚举倍数总和约为 $M \log M$。