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
| class KPrimes
{
static long long factor(long long x) {
int res = 0;
for(int i = 2; i * i <= x; i++) {
if(x % i) continue;
while(x % i == 0) {
res += 1, x /= i;
}
}
if(x != 1) res += 1;
return res;
}
public:
static std::vector<long long> countKprimes(int k, long long start, long long end) {
std::vector<long long> res;
for(int i = start; i <= end; i++) if(factor(i) == k) res.push_back(i);
return res;
}
static int puzzle(int s) {
int res = 0;
auto a = countKprimes(1,1,s), b = countKprimes(3,1,s), c = countKprimes(7,1,s);
for(int i = 0; i < a.size(); i++) {
for(int j = 0; j < b.size() and a[i] + b[j] <= s; j++) {
int x = s - a[i] - b[j];
auto it = std::lower_bound(std::begin(c), std::end(c), x);
if(it != std::end(c) and *it == x) res += 1;
}
}
return res;
}
};
|
