【牛客网】 Wannafly挑战赛9->A-找一找
链接：https://www.nowcoder.net/acm/contest/71/A
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
给定n个正整数，请找出其中有多少个数x满足：在这n个数中存在数y=kx，其中k为大于1的整数
输入描述:
第一行输入一个n
接下来一行输入n个正整数ai
输出描述:
输出符合条件个数 示例1
输入
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;
} 
