「一本通 6.2 练习 2」轻拍牛头

题目描述

今天是 $Bessie$ 的生日，并且现在是聚会的游戏时间。$Bessie$ 让编号为 $1N$ 的 $N$ 头奶牛围成一个圈坐（所以除了最后一头牛，第 $i$ 头奶牛与第 $i?1$ 和 $i+1$ 头奶牛相邻，第 $N$ 头奶牛和第 $N?1$ 头与第 1 头奶牛相邻）。同时，$Farmer$ $John$ 拿了个桶，在桶里装了十亿张小纸条，每张小纸条上写有某个范围在 $[1,10^6]$的整数。

接着，每头奶牛轮流从这个巨桶中抽取一个数 $A_i(1\le A_i\le 10^6)$（当然这些数没必要两两不同）。然后第 $i$ 头奶牛走一圈，如果奶牛 $i$ 手中的数字能够被奶牛 $j(j\ne i)$ 手中的数字整除，那么奶牛 $i$ 会拍奶牛 $j$ 的头。走完一圈后，奶牛 $i$ 回到原来的位置。

奶牛们想让你帮他们计算，对于每头奶牛，它需要拍多少头奶牛的头？

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：

5
2
1
2
3
4

输出样例#1：

2
0
2
1
3

提示信息

第一头奶牛会拍第二、第三头奶牛，第二头牛不会拍任何奶牛的头，等等。对于全部数据，$1\le N\le 10^5$。

解法

#include <bits/stdc++.h> 
using namespace std;
const int N=2e5,M=2e6;
int n,a[N],k[M];
int main() {
	cin >>n;
	for (int i=1;i<=n;i++) {
		cin >>a[i];
		k[a[i]]++;
	}
	for (int i=1;i<=n;i++) {
		int tt=0,j;
		for (j=1;j*j<=a[i];j++) {
			if(a[i]%j==0)
				tt+=k[j]+k[a[i]/j];
		}
		j--;
		if (j*j==a[i]) tt-=k[j];
		cout <<tt-1 <<endl;
	}
	return 0;
}