Description：

给出 $n$ 个数，对每个数求其他 $n-1$ 个数中能整除它的数的个数。

$1\leqslant n \leqslant 100000,1\leqslant a[i]\leqslant 10^6$

Solution：

$n^2$ 求肯定是不行的，开一个 $10^6$ 大小的桶，记录每个数字出现的个数，然后依次枚举每个数字把他的所有倍数都加上它，这样时间复杂度由调和级数 $\begin{align}\sum_{i=1}^n\frac n i=\ln n+\gamma\end{align}$ 得是 $O(n\log n)$ 的。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int n;

#define MAXN 100010

int a[MAXN];

#define MAX 1000001

int cnt[MAX];

int ans[MAX];

int main()

{

	scanf("%d",&n);

	memset(cnt,0,sizeof(cnt));

	memset(ans,0,sizeof(ans));

	for(int i = 1;i <= n;++i)++cnt[a[i] = read()];

	for(int i = 1;i < MAX;++i)

	{

		if(cnt[i])

		{

			for(int j = i;j < MAX;j += i)

			{

				ans[j] += cnt[i];

			}

		}

	}

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

	return 0;

}