新しいブログシステムの使い方を確認するためにも、UVa問題を解いてみる。

1. 問題
 整数a, b (0<a?b?100000) が与えられて、その間に含まれている平方数の数を答えろ。

2. 例2つ
 a=1, b=4の時に、含まれている平方数は1, 4の二つなので、答えは2になる。
 a=1, b=10の時に、含まれている平方数は1, 4, 9の3つなので、答えは3になる。

3. 考え方
 a=1, b=nに対する解答 f(n) が分かれば、本問題の答えは f(b)-f(a-1) になるので、f(n)についての解答を考えることにする。

100000の平方根は316。平方数は高々316しかないので、サイズ100000の配列を用意し、数えていけばうまくいくはず。

つまり、以下の漸近式が使える。

4. テストデータとその結果

5. 感想
 とても簡単な問題。

Comments are closed.

Post Navigation