　$2^{k}$ を約数として持つ $1$ 以上 $n$ 以下の整数の個数を $C_{n,k}$ で表すことにすると，
$$\sum_{k = 1} ^ {n} f(k) = \sum_{k = 0}^{\infty} 2^{k}C_{n,k}$$
となる．ここで，$C_{n,k} = \bigg \lfloor {\cfrac{n}{2^{k}}} \bigg \rfloor$ であるから，正の整数 $x,y$ に対して $x\\% y$ で $x$ を $y$ で割ったあまりを表すことにすると，
$$2^{k}C_{n,k} = n - n\\% 2^{k}$$
である．今，$2^{1000} \le n \lt 2^{1001} - 1$ の場合は，$C_{n,k} \gt 0$ となる $k$ の範囲は $0 \leq k \leq 1000$ であるので，
$$g(n) = -1000n + \sum_{k = 0}^{1000} (n - n \\% 2^{k}) = n - \sum_{k = 0}^{1000} n \\% 2^{k}$$
と分かる．\
　ここで，$n$ の $2$ 進数表記を $b_{1000}b_{999} \cdots b_{0}$ とする．このとき，$n\\%2^0 = 0$ であり，$k\ge1$ のときには
$$n\\%2^{k} = \sum_{i = 0}^{k - 1}2^{i}b_i$$
となるため，
$$\sum_{k = 0}^{1000} n\\% 2^{k} = \sum_{k = 0}^{1000}2^{k}(1000-k)b_{k}$$
を得る．これより，$b_{1000} = 1$ であることに気をつければ，
$$g(n) = n - \sum_{k = 0}^{1000} \ n ％ 2^{k} = 2^{1000} - \sum_{k = 0}^{999}2^{k}(999 - k)b_{k}$$
が分かる．ここで，$\displaystyle\sum_{k = 0}^{999}2^{k}(999 - k)b_{k}$ の各項の $b_k$ の係数は，$k$ に対して ($k = 999$ を除き) 広義単調増加である．また，
$$ \sum_{k = 0}^{4}2^{k}(999 - k) \lt 2^{5}(999-5),\quad \sum_{k = 0}^{1}2^{k}(999 - k) \lt 2^{2}(999-2)$$
がそれぞれ成り立つので，$g(n)$ のとり得る $37$ 番目に大きい値は
$$2^{1000} - (2^5(999-5) + 2^2(999-2)) = 2^{1000} - 35796$$
であり，これを $997$ で割ったあまりはフェルマーの小定理により $\bf112$ と分かる．

**補足.**　最後の議論と同様に考えることで，$n - 2^{1000}$ が十分に小さい範囲では $g(n)$ は狭義単調減少であることがわかる．
公式解説
https://onlinemathcontest.com/contests/omc217/editorial/8799
　正の整数 $n$ に対し，$n$ の正の約数のうち非負整数 $k$ を用いて $2^{k}$ と表されるものの総和を $f(n)$ とします．また，$g(n) = - 1000n + \displaystyle \sum_{k = 1} ^ {n} f(k)$ と定めます．\
　正の整数 $n$ が $2^{1000} \le n \lt 2^{1001}$ をみたしながら動くとき，$g(n)$ のとり得る $37$ 番目に大きい値を素数 $997$ で割った余りを解答して下さい．