链接：

来源：牛客网

题目描述

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

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define maxn 1000010#define debug(a) cout << #a << " " << a << endlusing 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
            
             > 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;}