問題概要
正整数 $L, R, d$ が与えられる.$L$ 以上 $R$ 以下の整数の内,$d$ の倍数の個数を求めよ.
制約
- $1 \leq L \leq R \leq 100$
- $1 \leq d \leq 100$
解法
制約が小さいので,$L$ 以上 $R$ 以下の整数を全通り試してそれぞれ判定することでも問題を解くことができますが,ここでは別の方法を紹介します.
この手の問題の場合,$0$ 以上 $n$ 以下の範囲での個数を数えることができれば,元々の問題の答えを簡単に求められる場合が多いです.関数 $f_d$ を以下のように定めます.
- $f_d( n ) := $ $0$ 以上 $n$ 以下の整数の内,$d$ の倍数の数
このようにすると,$f_d$ の値も以下のように簡単に計算できます.
- $f_d( n ) = \lfloor \frac n d \rfloor$
切り下げ記号は整数で演算すれば自動的にやってくれるようなものなので,実質割り算だけになりました.で,元々の問題の答えは,$$f_d( R ) - f_d( L - 1 )$$ で求まります.
この方法の場合,定数回の整数演算で答えが求まるので,$O( 1 )$ 時間で実行できます.
コード
main = do [ l, r, d ] <- readInts print $ ( r `div` d ) - ( ( l - 1 ) `div` d )