Codeforces Round #276 (Div. 1) B. Maximum Value

問題概要
N個の要素をもつ配列が与えられる. このとき, $a_{i} \geq a_{j}$ を満たすような $(i, j)$ について, $a_{i} \bmod a_{j}$ の最大値を求める.

制約: $1 \leq N \leq 10^5, 1 \leq A_{i} \leq 10^6$

考えたこと
全ての組み合わせを試すことはできないので, 探索範囲を小さくすることを念頭に置く.
$a_{j}$ で割った余りが最大になるのは, $a_{i} = k*a_{j} + (a_{j}-1)$ であるように,
$k*a_{i} \leq a_{j} < (k+1)*a_{i}$ の区間において, $(k+1)*a_{i}$ に最も近い $a_{j}$ を求めればよいことが分かる.