Count_multiples

$[1]$ 四則演算だけで解く定数時間 $O(1)$ 解法

まずは次のような単純化した問いを考えましょう。
「$1$ から$N$ までの中に, $X$の倍数は何個あるか？」
この問いの答えは, $N$ を $X$ で切り捨て除算 (小数点以下切り捨ての割り算)した値として得ることが出来ます。
例えば「$1$ から$15$ までの中に, $4$ の倍数は何個あるか？」だと
15 // 4 を計算して, $3$ 個となることが分かります。

これを利用して 「$A$ から$B$ までの中に, $X$の倍数は何個あるか？」という今回の問題に答えます。
「$1$ から $B$ までの中に, $X$の倍数は何個あるか？」の答えから
「$1$ から $A - 1$ までの中に, $X$の倍数は何個あるか？」の答えを
引くことによって, $A$ 以上 $B$ 以下の範囲内にある$X$の倍数の個数を求めることが出来ます。

xxxxxxxxxx

A = int(input())

B = int(input())

X = int(input())

​

C = B // X        # 1 以上 B 以下のうち, Xの倍数であるものの個数

D = (A - 1) // X  # 1 以上 A-1 以下のうち, Xの倍数であるものの個数  (A = 1のときは0個)

​

print(C - D)

$[2]$ ループを回す $O(B - A)$ 解法

$A$ 以上 $B$ 以下の自然数について, 「$X$で割り切れるか？」を一つずつ確認していく方法もあります。
この方法を取るには ループ と 条件分岐 について学ぶ必要があります。

xxxxxxxxxx

A = int(input())

B = int(input())

X = int(input())

​

ans = 0

​

for n in range(A, B + 1):  # AからBまでループを回す

    if n % X == 0:  # もしもXの倍数ならば

        ans = ans + 1  # 答えを1増やす

​

print(ans)

【発展】計算量についての補足

今回の問題では $1≦A≦B≦100000$ という制約がありました。
つまり, ループを回す解法だと計算量最悪の場合($A = 1, B = 100000$)で $100000$回のループを回す必要があります。
($1$ は$X$ で割り切れるか？, $2$ は割り切れるか？, $3$ は... を$B$ の値まで延々と繰り返していく)
ループを回す回数が多くなるほど計算に要する時間は増えていきます。
($A$ = $1$, $B$ = $100$兆 のとき, $1$から$100$兆 まで一つずつ調べていると現実的な計算時間では終わりません)
しかし, 四則演算だけで解いた方法だとループを1度も回さないので, $B$の値がどんなに大きくなっても一瞬で答えを求めることが出来ます。
四則演算だけで解いた方法は, 計算量が改善された「賢い」方法なのです。

このように問題解決に どのようなアプローチをとるか (= どんな アルゴリズム を考案・設計するか) が重要です。