問題概要
正整数 $N$ が与えられる．$A \times B + C = N$ を満たすトリプレット $( A, B, C )$ の個数を求めよ．
制約
- $2 \leq N \leq 10^6$
解法
数学はむずかしいので全探索による解法を考えます．与式の $A$ となり得る正整数 $a$ をすべて試すとすると，$a$ の候補は $\Theta( N )$ 個あります．$a$ が固定された上で更に $B$ の候補となる $b$ をとるとすると，（与式を変形した）$A \times B = N - C$ ($0 \leq C$) より，$a \times b < N$ です（この範囲で $a, b$ をとれば $c$ は自動的に決まります）．各 $a$ に対し，$b = 1, 2, 3, \dots$ と試していくことにすると，$a$ に対して試される $b$ の個数はたかだか $\frac N a$ 個程度です．自然数の逆数和は 調和数 で，発散速度は項数 $n$ に対し $O( n \log n )$ なので，上記の全探索で探索される値の個数も実は $O( N \log N )$ 個となり，間に合います．
コード
main = do n <- readInt print $ length $ do a <- [ 1 .. n ] takeWhile ( \b -> a * b < n ) [ 1 .. n ] return ()
