SRM437 Div2 Hard

1000

メモ化する。
n の m 乗根を探していけばいい。

解法はすぐに思いつくけど、通すのは難しい気がする。
本番通した人はエスパーに違いない。

map<lli, lli> memo;

lli lpow(lli n, lli p)
{
  if (p == 0) return 1;
  if (p == 1) return n;
  lli m = lpow(n, p / 2);
  return p % 2 ? (m * m * n) : (m * m);
}

lli rec(lli n)
{
  if (n == 0) return 0;
  if (n == 1) return 0;
  if (n == 2) return 1;
  if (n == 3) return 2;
  if (n == 4) return 2;
  if (n == 5) return 3;
  if (memo.count(n)) return memo[n];

  const lli ln = (lli)ceil(log10(n) / log10(2));

  lli mn = n - 1;
  for (lli p = 2; p <= ln; ++p) {
    lli x = (lli)floor(pow(n, 1.0 / p));
    lli y = (lli)ceil(pow(n, 1.0 / p));
    lli a = rec(x) + abs(n - lpow(x, p));
    lli b = rec(y) + abs(n - lpow(y, p));
    mn = min(mn, min(a + 1, b + 1));
  }

  return memo[n] = mn;
}

class ThePower {
public:
  int count(long long N)
  {
    memo.clear();
    return rec(N);
  }
};