牛客网 Wannafly挑战赛 A 找一找 思考题

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

题目描述

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

输入描述:

第一行输入一个n

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

输出描述:

输出符合条件个数

输入例子:

5

1 2 3 4 5

输出例子:

2

-->

示例1

输入

5

1 2 3 4 5

输出

2

说明

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

备注:

1≤n,a

≤1000000

emmmmm，直接上代码把，用下标记数组，第二层循环用倍增，因为是倍增，所以最坏的时间复杂度是n/2+n/3+n/4...+n/n，在10^8左右所以可以通过题目了

#include<queue>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define maxn 1000010

#define debug(a) cout << #a << " " << a << endl

using namespace std;

typedef long long ll;

int a[maxn];

int main() {

    int n;

    while( cin >> n ) {

        memset(a,,sizeof(a));

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

            int x;

            cin >> x;

            a[x] ++;    //打标记

        }

        int ans = ;

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

            if( a[i] ) {

                for( int j=i+i; j<=; j+=i ) { //倍增找倍数指

                    if( a[j] ) {

                        ans += a[i];

                        break;

                    }

                }

            }

        }

        cout << ans << endl;

    }

    return ;

}