AtCoder Beginner Contest 182, B : Almost GCD

問題文

　https://atcoder.jp/contests/abc182/tasks/abc182_b

問題概要

　$N$ 項からなる正整数の列 $\{ A_i \}$ が与えられる．$2$ 以上の整数であって，$A_i$ を割り切る $i$ の個数が最大のものを求めよ．

制約

• $1 \leq N \leq 100$
• $1 \leq A_i \leq 1000$

解法

　$\max\{ A \}$ を超える整数については $A_i$ を割り切ることはないので，例えば $A_0$ を選んだ場合よりも悪い解となります．よって，最適解になり得るのは $\max\{ A \}$ 以下の整数です．
　解の候補をひとつ決めると，各 $A_i$ を割り切るかどうかを試しながら割り切れるものの個数を数えることでスコアを求められます．よって，解候補をすべて試すことで答えが求まります．
　計算量としては，$O( \max\{ A \} N )$ となります．

コード

main = do
	n <- readInt
	as <- readInts
	print $ snd $ maximum $ do
		k <- [ 2 .. 1000 ]
		let
			res = length $ filter ( ( == 0 ) . ( `mod` k ) ) as 
		return $ ( res, k )