链接：

来源：牛客网

题目描述

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

输入描述:

第一行输入一个n

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

_i

输出描述:

输出符合条件个数

示例1

输入

51 2 3 4 5

输出

2

说明

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

备注:

1≤n,a

_i

≤1000000

#include
      
       using namespace std;typedef long long  ll;const int inf = 0x3f3f3f3f;const int maxn = 40000 + 20;const int moder = 1e9 + 7;const int K = 256;const int MAXN=1000005;int cnt[MAXN];int main(){    int n;    cin >> n;    for(int i=0;i < n;i++)    {        int a;        cin >> a;        cnt[a]++;    }    int num = 0;    for(int i=1;i < MAXN;i++)    {        if(cnt[i] > 0)        {            for(int j=2*i;j < MAXN;j=j+i)            {                if(cnt[j] > 0)                {                    num += cnt[i];                    break;                }            }        }    }    cout << num << endl;    return 0;}
      

需要注意的是输入的i可能会重复因此是用 cnt [i] ++;