【牛客网】 Wannafly挑战赛9->A-找一找

输入描述:

输出描述:

输出符合条件个数

5
1 2 3 4 5

2

5个数中1和2符合条件，1是后面每个数的因子，2是4的因子

备注:

1≤n,ai≤1000000

题解：

原本的思路是所有数据for循环一遍并判断是否符合条件，可是时间复杂度太高O（n*n）超时了。

询问了一下大神，他用数组存下数据，然后进行判断相加。还要注意一点，数据可能相等，例如：出现

5

1 2 2 3 4

这里面有两个2，要注意。

#include<stdio.h>
#include<string.h>
int a[1000005];
int main()
{
	int t;
//	while(~scanf("%d",&t))
//	{
		scanf("%d",&t);
		int i,n,j,sum=0,max=0;
		memset(a,0,sizeof(a));
		while(t--)
		{
			scanf("%d",&n);
			a[n]++;
			if(n>max)
			max=n;
		}
		for(i=1;i<1000005;i++)
		{
			if(a[i]!=0)
			{
				for(j=i*2;j<=max;j=j+i)
				{
					if(a[j]!=0)
					{
						sum=sum+a[i];
						break;
					}
				}
			}
		}
		printf("%d\n",sum);
//	}
	return  0;
}