// ////////////////////////////////////////////////////////
// # Title
// Maximum length of an antichain
//
// # URL
// https://projecteuler.net/problem=386
// http://euler.stephan-brumme.com/386/
//
// # Problem
// Let `n` be an integer and `S(n)` be the set of factors of `n`.
//
// A subset `A` of `S(n)` is called an antichain of `S(n)` if `A` contains only one element or if none of the elements of `A` divides any of the other elements of `A`.
//
// For example: `S(30) = \{1, 2, 3, 5, 6, 10, 15, 30\}`
// `\{2, 5, 6\}` is not an antichain of `S(30)`.
// `\{2, 3, 5\}` is an antichain of `S(30)`.
//
// Let `N(n)` be the maximum length of an antichain of `S(n)`.
//
// Find `sum{N(n)}` for `1 <= n <= 10^8`
//
// # Solved by
// Stephan Brumme
// November 2017
//
// # Algorithm
// Each number can be factorized into prime numbers. A factor `f_i` doesn't divide any other factor `f_j` if:
// - `f_i` and `f_j` don't share any prime factors or
// - if they share prime factors then at least one not not all of their exponents of `f_i` are greater-or-equal than `f_j`
// - e.g. `60 = 2^2 * 3^1 * 5^1`: if `f_i = 2^1 * 3^1` and `f_j = 5^1` then they are a valid antichain
// - but if `f_i = 2^2 * 3^1` and `f_j = 2^1 * 3^1` then they aren't
//
// The ''search()'' computes all factorizations by recursively merging prime numbers in every possible way such that the product remains below ''limit''.#
// Those factors are forwarded to ''evaluate()'' which converts the factors to their exponents, e.g. `60 = 2 * 2 * 3 * 5 = 2^2 * 3^1 * 5^1` becomes ''{2, 1, 1}''.
// The interesting thing is that the bases don't matter (they were 2, 3 and 5 in that case) during antichain computation.
// Even more, I can't easily re-order them: ''std::sort'' puts them in ascending order such that the total number of distinct exponents is just over 800
// (so that memoization can keep the runtime low).
//
// The core functionality is hidden in ''antichain()'': based on a list of exponents it recursively determines the maximum length of an antichain.
// Over the course of multiple days I wrote that function with lots of trial'n'error. It looks simple now but trust me, I typed heaps of ugly code before coming up with the final version ...
// It basically "chops off" the exponents from the list by observing that the sum of the exponents of the longest antichain is at most half that of the total sum.
//
// # Note
// Some code is devoted to memory efficiency, e.g. re-using static containers. It's definitely not the most readable solution I published !
#include
#include
#include