ABC048-B - Between a and b ... を解く - 考えて競プロする

ABC048-B - Between a and b ...

a 以上 b 以下の整数のうち、x で割り切れるものの個数を求める問題

a から b までの全ての整数について、x で割り切れるか確認していけば簡単なのだが

制約が 0 <= a <= b <= 10^18 なのでそれでは間に合わない…

ここは数学的な解法を考える必要がありそうだ

例えば 1〜100 の数字で 3 で割り切れるものの数は

100 ÷ 3 = 33.333… で 33 個であると求められる

このように割り算を使って割り切れる個数を求めていく

今回は a 〜 b の範囲で割り切れる個数を求める必要があるので

先程の例より少し複雑である

そこで、先程の例をもう少し詳しく見てみることにする

1 〜 100 で 3 で割り切れる数の内、最初に現れるものは 3 である

最後に現れるものは 99 だ

この 3 と 99 はつまり 3 × 1 と 3 × 33 である

したがって 1 〜 100 で 3 で割り切れる数 3, 6, 9, … , 96, 99 の個数は

33 - 1 + 1 = 33 で 33 個であるとわかる

（なぜ + 1 をするかわからない人は「植木算」でググること）

したがって、範囲内の数字について、最初に割り切れる数（上記の場合は「3」）と

最後に割り切れる数（上記の場合は「99」）がわかれば

割り切れる数の個数がわかる

最後に、上記の 3（ = 3 × 1）と 99（ = 33 × 3）にあたる数字はどうやって得るか

これは範囲の端の数を 3 で割ってみればいい

① 1 ÷ 3 = 0.333...

② 100 ÷ 3 = 33.333...

①小さい方を切り上げると 1 に

②大きい方を丸めると 33 になるので

このルールに従うことにする

以上を踏まえて書いたコードを以下に示す

提出したコード

# 入力
a,b,x=map(int,input().split())

# 出力
print(b//x-(-(-a//x))+1)

切り上げ、切り捨ての実現のために負の符号を意図的に付けたり

"//" による除算を行なっていることに注意

提出結果はACでした

解説スライドでは明快な解説が書かれているので見てみるといいかも