-
Notifications
You must be signed in to change notification settings - Fork 0
/
Euler_78.cpp
60 lines (47 loc) · 1.06 KB
/
Euler_78.cpp
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
#include "Euler.h"
cpp_int partition(cpp_int &n, std::vector<cpp_int> &cache)
{
cpp_int p = 0;
if (n >= 0)
{
if (n == 0 || n == 1)
{
return 1;
}
if (cache[n.toInt() - 1] != 0)
{
return cache[n.toInt() - 1];
}
int k = 1;
cpp_int s1 = 0;
cpp_int s2 = 0;
while (n - s2 >= 0)
{
s1 = (k * (3 * k - 1)) / 2;
s2 = (k * (3 * k + 1)) / 2;
cpp_int sign = (k - 1) & 1 ? -1 : 1;
p += sign * partition(n - s1, cache);
p += sign * partition(n - s2, cache);
++k;
}
cache[n.toInt() - 1] = p;
}
return p;
}
llui Euler::CoinPartitions()
{
int ceiling = 100000;
std::vector<cpp_int> cache(ceiling, 0);
for (int i = 1; i < ceiling; ++i)
{
if ((i - 4) % 5 == 0)
{
cpp_int n = partition(cpp_int(i), cache);
if (n % 1000000 == 0)
{
return i;
}
}
}
return 0;
}