回答編集履歴
1
実際に書いてみた
test
CHANGED
|
@@ -3,3 +3,27 @@
|
|
|
3
3
|
|
|
4
4
|
|
|
5
5
|
二進法で表現して1が17個になる最小の数は1（2の0乗）＋2（2の1乗）＋…＋65536（2の16乗）ですが、これは131071と、100000を超えてしまいます。つまり、100000未満には1つもありません。
|
|
6
|
+
|
|
7
|
+
|
|
8
|
+
|
|
9
|
+
----
|
|
10
|
+
|
|
11
|
+
（combinationで書いたコード）
|
|
12
|
+
|
|
13
|
+
|
|
14
|
+
|
|
15
|
+
```ruby
|
|
16
|
+
|
|
17
|
+
a = 1_000_000
|
|
18
|
+
|
|
19
|
+
b = 17
|
|
20
|
+
|
|
21
|
+
|
|
22
|
+
|
|
23
|
+
p (0..(a.bit_length - 1)).to_a.combination(b)
|
|
24
|
+
|
|
25
|
+
.map{ |arr| arr.map{ |i| 2**i }.reduce(&:+) }
|
|
26
|
+
|
|
27
|
+
.select{ |num| num <= a }.length
|
|
28
|
+
|
|
29
|
+
```
|