牛客网 Wannafly挑战赛9 A.找一找-数据处理

好几天没好好学习了(咸鱼晒干了)

把稍微没那么咸鱼的几天前的一场牛客网的比赛稍微看了一下，菜的要死，这一场大数的比较多，都死了。

A.找一找

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

链接：https://www.nowcoder.net/acm/contest/71/A
来源：牛客网

题目描述

给定n个正整数，请找出其中有多少个数x满足：在这n个数中存在数y=kx，其中k为大于1的整数

输入描述:

第一行输入一个n

接下来一行输入n个正整数a

输出描述:

输出符合条件个数

输入例子:

5

1 2 3 4 5

输出例子:

-->

示例1

输入

5

1 2 3 4 5

输出

说明

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

这道题如果两个直接比较数组里的数for，会超时，因为数组里可能有相同的数，所以数据处理一下，直接比较一次将数的个数加起来就可以，遍历数据范围那么大小就可以了，暴力。

代码:

 //A-这个题将数据压缩一下，可以减少循环次数

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 using namespace std;

 const int maxn=1e6+;

 const int maxm=1e6;

 int num[maxn];

 int main(){

     int n;

     while(~scanf("%d",&n)){

         for(int i=;i<n;i++){

             int x;

             scanf("%d",&x);

             num[x]++;

         }

         int ans=;

         for(int i=;i<=maxm;i++){

             if(num[i]){

                 for(int j=i*;j<=maxm;j+=i){

                     if(num[j]){

                         ans+=num[i];break;

                     }

                 }

             }

         }

         printf("%d\n",ans);

     }

     return ;

 }