約数の個数と数え上げの工夫
今回は、主客転倒が刺さる問題を解いていきます。それでは、よろしくお願いします。
問題
問題: 約数の個数と数え上げの工夫
\(f(x)\) を \(x\) の \(200\) 以上の約数の個数とする。このとき以下の値を計算せよ。 \[f(1)+f(2)+\cdots+f(1000)\]
工夫して数えるにはどうすればよいか？を考えると、主客転倒が使えそうなことが分かると思います。
解説
解答：\(1228\)
\(200\) 以上の整数が何回寄与するかを考えれば良い。例えば \(200\) は \(f(200),f(400),\cdots,f(1000)\) の計 \(5\) 回数えられると言った具合である。 \[ \sum_{n=200}^{1000}{\left \lfloor \frac{1000}{n}\right \rfloor}=5\cdot1+4\cdot50+3\cdot83+2\cdot167+1\cdot500=1288 \]