🐢
[鉄則A31] Divisors
数えるのではなく全体から引いて考える問題。
問題を要約する
- 1..N のなかで 3 または 5 で割り切れるのはいくつある？
何が難しい？
言葉通り 1..N を順番に 3 または 5 で割り切れるか試していくと固まる。
速い解き方
問題を「1..6 を 2 または 3 で割り切れる数を求めよ」に言い換えると、次の o の数が答えになりそうに思える。
| 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|
| 2 | o | o | o | |||
| 3 | o | o |
とりあえず o の数は、
(6 / 2) + (6 / 3) # => 5
で求まる。
しかし、よく見ると 6 で重複している。一方はいらない。この 6 は 2 * 3 である。つまり 2 * 3 の倍数で重複が起きているので重複個数は、
6 / (2 * 3) # => 1
で求まる。したがってこの重複分を最後に引けば、
5 - 1 # => 4
辻褄が合う。
単純な実装 (TLE)
N = gets.to_i
ans = (1..N).count do |e|
e.modulo(3).zero? || e.modulo(5).zero?
end
p ans # => 5
N が1千万で1秒超える。
解説の模範解答 (AC)
101 ms
N = gets.to_i
p (N / 3) + (N / 5) - (N / (3 * 5)) # => 14
ほとんど何もしてないのに 101 ms とは！？
Discussion