project-euler

https://projecteuler.net/
Log | Files | Refs | README

Euler_78.cpp (1081B)

      1 #include "Euler.h"
      2 
      3 cpp_int partition(cpp_int &n, std::vector<cpp_int> &cache)
      4 {
      5     cpp_int p = 0;
      6 
      7     if (n >= 0)
      8     {
      9         if (n == 0 || n == 1)
     10         {
     11             return 1;
     12         }
     13         if (cache[n.toInt() - 1] != 0)
     14         {
     15             return cache[n.toInt() - 1];
     16         }
     17 
     18         int k = 1;
     19 
     20         cpp_int s1 = 0;
     21         cpp_int s2 = 0;
     22 
     23         while (n - s2 >= 0)
     24         {
     25             s1 = (k * (3 * k - 1)) / 2;
     26             s2 = (k * (3 * k + 1)) / 2;
     27 
     28             cpp_int sign = (k - 1) & 1 ? -1 : 1;
     29 
     30             p += sign * partition(n - s1, cache);
     31             p += sign * partition(n - s2, cache);
     32             ++k;
     33         }
     34 
     35         cache[n.toInt() - 1] = p;
     36     }
     37 
     38     return p;
     39 }
     40 
     41 llui Euler::CoinPartitions()
     42 {
     43     int ceiling = 100000;
     44     std::vector<cpp_int> cache(ceiling, 0);
     45 
     46     for (int i = 1; i < ceiling; ++i)
     47     {
     48         if ((i - 4) % 5 == 0)
     49         {
     50             cpp_int n = partition(cpp_int(i), cache);
     51 
     52             if (n % 1000000 == 0)
     53             {
     54                 return i;
     55             }
     56         }
     57     }
     58 
     59     return 0;
     60 }