AtCoder Beginner Contest 170, D : Not Divisible

問題文

　https://atcoder.jp/contests/abc170/tasks/abc170_d

問題概要

　長さ $N$ の整数列 $\{ A_i \}$ が与えられる．$A$ のインデックス $i$ であって，$i \neq j$ である任意の $A$ のインデックス $j$ について $A_j \not \mid A_i$ （$A_j$ が $A_i$ を割り切らない）ものの数を求めよ．

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^6$

解法

　ある数が他のある数を割り切るためには，割られる数が他方の数以上である必要があるため，ある種の順序のような雰囲気があります．そこで，$A$ の値を昇順に調べることを考えます．
　ある数 $A_i$ に着目したとき，Eratosthens の篩のような気持ちでその倍数に印をつけておけば，未来でより大きな値について調べるときに，それが他の数で割り切られるかどうかを知ることができます．よって，篩のような操作をしつつ $A$ の値を昇順に調べて条件を満たすものを数えることで答えが求まります．
　計算量についてですが，整数 $i$ について篩うとき，そのループは $$\frac { \max\{ A \} } i$$ 回回ります．制約の範囲で全ての整数が出現したとすると，ループの回る回数は $$\sum_{ i = 1 }^{ \max\{ A_i \} } \frac { \max\{ A \} } i$$ になります．ここで分子の $\max\{ A \}$ を外に出すと，$$\max\{ A_i \} \sum_{ i = 1 }^{ \max\{ A_i \} } \frac 1 i$$ です．シグマの部分は自然数の逆数和で，これは調和数の定義そのものです．また，調和数の発散速度は $O( \log n )$ なので，上記式の発散速度は $O( \max\{ A \} \log \max\{ A \} )$ になります．

コード

int main()
{
	IN( int, N );
	VI A( N );
	cin >> A;

	static int counts[ 1 << 20 ], sieve[ 1 << 20 ];
	for_each( ALL( A ), [&]( const int a ){
			++counts[a];
			++sieve[a];
			} );

	int res = 0;
	REP( i, 1 << 20 )
	{
		if ( !counts[i] )
		{
			continue;
		}

		res += sieve[i] == 1;

		for ( int j = 1; i * j < ( 1 << 20 ); ++j )
		{
			++sieve[ i * j ];
		}
	}

	cout << res << endl;

	return 0;
}