337-test.cpp

/*
 * Project Euler - Problem 337 (test, O(N^2))
 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <cinttypes>

using namespace std;

const uint32_t N = 2e7;
const uint32_t M = 1e8;

vector<uint32_t> phis(N+1, 1);

void init_phis(void)
{
  for (size_t i = 2; i <= N; i++) {
    if (phis[i] != 1) continue;
    phis[i] *= i-1;
    for (size_t j = i+i; j <= N; j += i) phis[j] *= i-1;
    for (size_t pow = i*i; pow <= N; pow *= i) {
      for (size_t j = pow; j <= N; j += pow) phis[j] *= i;
    }
  }
}

uint64_t solve(void)
{
  vector<uint32_t> dp(N+1, 0);
  dp[6] = 1;

  // search φ(a) < φ(b) < a < b
  for (uint32_t b = 8; b <= N; b++) {
    uint32_t acc = 0;
    for (uint32_t a = phis[b]+1; a < b; a++) {
      if (phis[a] < phis[b]) {
        acc = (acc + dp[a]) % M;
      }
    }
    dp[b] = (dp[b] + acc) % M;
  }

  return accumulate(begin(dp), end(dp), 0, [](uint32_t x, uint32_t y){ return (x+y)%M; });
}

int main(void)
{
  init_phis();
  cout << solve() << endl;
}