AtCoder ABC170 D - Not Divisible 题解

link

description：

求出一个数列中有多少数 $\bmod$ 数列中其他任何位置的数都不等于 $0$。

solution：

观察到直接 $O(n^2)$ 暴力枚举会超时，那么不妨先对数列进行排序，然后对于每一个数，均枚举倍数直至 $a_n$。这样的话就能优化时间复杂度。

code：

#include<cstdio>
#include<algorithm>
using namespace std;
int a[200005],b[1000005];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
	{
		for(int j=a[i];j<=a[n];j+=a[i])
		{
			b[j]++;
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		if(b[a[i]]==1)
		ans++;
	}
	printf("%d\n",ans);
	return 0;
}