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

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

题目描述

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

输入描述:

第一行输入一个n

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

输出描述:

输出符合条件个数

示例1

输入

5
1 2 3 4 5

输出

2

说明

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

备注:

1≤n,a

_i

≤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,0,sizeof(a));
        for( int i=0; i<n; i++ ) {
            int x;
            cin >> x;
            a[x] ++;    //打标记
        }
        int ans = 0;
        for( int i=1;i<=1000000;i++) {
            if( a[i] ) {
                for( int j=i+i; j<=1000000; j+=i ) { //倍增找倍数指
                    if( a[j] ) {
                        ans += a[i];
                        break;
                    }
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}