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
|
#include "aoc.h"
#include <algorithm>
#include <set>
#include <vector>
namespace aoc2015 {
std::pair<int, int> by2(int x, int factor) {
int a = 0;
while (true) {
int total = 0;
for (int i = 0; i <= a; i++) {
total += 1 << i;
}
// printf("%d -> %d\n", a, total * 10);
if (total * factor > x) {
return {1 << (a - 1), 1 << a};
}
a++;
}
}
std::vector<int> primefactor(int x) {
std::vector<int> v;
while (x % 2 == 0) {
v.push_back(2);
x /= 2;
}
for (int i = 3; i * i <= x; i += 2) {
while (x % i == 0) {
v.push_back(i);
x /= i;
}
}
if (x > 2) {
v.push_back(x);
}
return v;
}
// backtrace
void combo(size_t m, size_t x, std::vector<int>& is, std::set<int>& rs, const std::vector<int>& ps) {
if (is.size() >= m) {
int x = 1;
std::for_each(is.begin(), is.end(), [&x, &ps](int i) { x *= ps[i]; });
rs.insert(x);
} else {
for (size_t i = x; i < ps.size(); i++) {
is.push_back(i);
combo(m, i + 1, is, rs, ps);
is.pop_back();
}
}
}
int combo(int i, int factor) {
std::vector<int> ps = primefactor(i);
std::vector<int> is;
std::set<int> rs;
rs.insert(1);
rs.insert(i);
for (size_t i = 1; i < ps.size(); i++) {
combo(i, 0, is, rs, ps);
}
int total{0};
std::for_each(rs.begin(), rs.end(), [&total, factor](int x) {
// int d = i / x;
// if (d <= 50) {
total += x * factor;
// }
});
return total;
}
int left_bound(std::pair<int, int> p, int target, int factor) {
// int left = p.first;
// int right = p.second;
// while (left <= right) {
// int mid = left + (right - left) / 2;
// int x = combo(mid);
// if (x > target) {
// right = mid - 1;
// } else if (x < target) {
// left = mid + 1;
// } else if (x == target) {
// right = mid - 1;
// }
// }
for (int i = p.first / 2; i < p.second; i++) {
int x = combo(i, factor);
// printf("%d %d\n", i, x);
if (x >= target) {
return i;
}
}
return p.second;
}
std::pair<int, int> day20(int x, int factor) {
auto p = by2(x, factor);
int m = left_bound(p, x, factor);
return {m, 884520};
}
} // namespace aoc2015
|
