方針
に含まれる素数の個数は,の倍数,の倍数,の倍数,…を数えて足せばよい。ではの倍数だけを数えればよく,等比数列の和になる。
解答
(1)
に含まれる素因数3の個数を数える。の中で3の倍数は3個,9の倍数は1個である。したがってである。
(2)
に含まれる素因数5の個数を数える。の中で5の倍数は5個,25の倍数は1個である。したがってである。
(3)
とする。に含まれる素因数の個数は,の中での倍数の個数,の倍数の個数,…,の倍数の個数を足したものである。
の倍数は個あるので,である。等比数列の和としてである。
別解
別解(段階ごとの漸化式)
方針
(1) (2) は に含まれる を,最初の1段と の倍数に残る分に分けて数える。(3) は とおき, から までの の倍数から1個ずつ を取り出して の漸化式を作る。
解答
(1) のうち3の倍数は の3個で,それぞれ少なくとも1個の3をもつ。さらに にはもう1個の3がある。したがって(2) 同様に, のうち5の倍数は5個で, にだけもう1個の5がある。よって(3) とおく。 から までのうち, の倍数はの 個である。それぞれからまず1個ずつ を取り出すと,残る積は である。したがってまた である。これを順に用いるとゆえに
総評
難度5,計算量4。想定時間は14分程度。優先度は「必ず完答したい」。(1)(2) は倍数の個数を数える標準計算で, の倍数をもう一度数えることが採点上の基本点になる。差がつく (3) では, の倍数が 個あることを明記するか, を立てる。公式名だけで済ませず,なぜ重複して数えるかを一文で説明したい。