Zenn
🐢

[鉄則B31] Divisors Hard

2024/05/25に公開
Ruby
AtCoder
競プロ
包除原理
tech

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_dd

2つから3つになった途端急にややこしくなる問題。

問題を要約する

  • 1..N のなかで 3, 5, 7 いずれかで割り切れるのはいくつある？

間違った解き方

前問の解法を復習すると「3, 5 のいずれかで割り切れる数」の場合は、

N = 35
o = (N / 3) + (N / 5)  # => 18
x = N / (3 * 5)        # => 2
o - x                  # => 16

で求まった。今回は 3, 5, 7 なので同様に、

N = 35
o = (N / 3) + (N / 5) + (N / 7)  # => 23
x = N / (3 * 5 * 7)              # => 0
o - x                            # => 23

求めると 23 になる。しかし、確実な方法で出した答えとは、

(1..35).count { |e| [3, 5, 7].any? { |m| e.modulo(m).zero? } }  # => 19

違うようだ。実際に数えてみても、

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
o o o o o o o o o o o
o o o o o o o
o o o o o

19 になる。

どこでおかしくなった？

重複が起きている箇所を列挙してみると 15, 21, 30, 35 で、つまり全体から 4 を引かないといけない。ところが N / (3 * 5 * 7) は 0 なので何も引いていなかった。

正しい解き方 (嘘)

15, 21, 30, 35 の 4 つは次の方法で求まる。

N / (3 * 5)  # => 2
N / (3 * 7)  # => 1
N / (5 * 7)  # => 1
2 + 1 + 1    # => 4

つまり 3 * 5 * 7 を分母にするのではなく 3, 5, 7 を総当たりで掛け算した結果を分母にするのが正しい。これで、

N = 35
all = (N / 3) + (N / 5) + (N / 7)  # => 23
all -= N / (3 * 5)                 # => 21
all -= N / (3 * 7)                 # => 20
all -= N / (5 * 7)                 # => 19

19 になる。ところが N = 210 で考えるとまたもおかしい。

(1..210).count { |e| [3, 5, 7].any? { |m| e.modulo(m).zero? } }  # => 114

N = 210
all = (N / 3) + (N / 5) + (N / 7)  # => 142
all -= N / (3 * 5)                 # => 128
all -= N / (3 * 7)                 # => 118
all -= N / (5 * 7)                 # => 112

114 のはずが 112 になる。

差分 2 の謎

表を確認すると、

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210
o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o

105 が 3, 5, 7 どれでも割り切れるため、

105.modulo(3)  # => 0
105.modulo(5)  # => 0
105.modulo(7)  # => 0

3 回引かれている。つまり、105 とその倍数の 210 は無いことになっている。したがって、引きすぎたぶんを今度は足さないといけない。105 と 210 の 2 つ は最初に間違えた方法の、

N / (3 * 5 * 7)  # => 2

で求まる。

正しい解法 (本当)

以上をまとめると、

N = 210

# 全部 (重複あり)
all = (N / 3) + (N / 5) + (N / 7)  # => 142

# いらないのを除外する
all -= N / (3 * 5)                 # => 128
all -= N / (3 * 7)                 # => 118
all -= N / (5 * 7)                 # => 112

# 除外しすぎたので足す
all += N / (3 * 5 * 7)             # => 114

となる。なんとも美しさに欠ける解法だが解説に書いてある通りなのだから仕方ない。

単純な実装 (TLE)

N = gets.to_i
ans = (1..N).count do |e|
  [3, 5, 7].any? { |d| e.modulo(d).zero? }
end
p ans  # => 114

N が1千万で2秒を超える。

解説の模範解答 (AC)

132 ms
N = gets.to_i                      # => 210

# 全部 (重複あり)
all = (N / 3) + (N / 5) + (N / 7)  # => 142

# いらないのを除外する
all -= N / (3 * 5)                 # => 128
all -= N / (3 * 7)                 # => 118
all -= N / (5 * 7)                 # => 112

# 除外しすぎたので足す
all += N / (3 * 5 * 7)             # => 114

p all                              # => 114

リファクタリング後 (AC)

122 ms
N = gets.to_i                                       # => 210
D = [3, 5, 7]
all = D.sum { |e| N / e }                           # => 142
all -= D.combination(2).sum { |a, b| N / (a * b) }  # => 112
all += N / D.inject(:*)                             # => 114
p all                                               # => 114

3, 5, 7 をまとめたもの。

参考

Discussion