SRM437 Div2 Hard

1000

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

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

view plainprint?

1. map<lli, lli> memo;  
2.   
3. lli lpow(lli n, lli p)  
4. {  
5.   if (p == 0) return 1;  
6.   if (p == 1) return n;  
7.   lli m = lpow(n, p / 2);  
8.   return p % 2 ? (m * m * n) : (m * m);  
9. }  
10.   
11. lli rec(lli n)  
12. {  
13.   if (n == 0) return 0;  
14.   if (n == 1) return 0;  
15.   if (n == 2) return 1;  
16.   if (n == 3) return 2;  
17.   if (n == 4) return 2;  
18.   if (n == 5) return 3;  
19.   if (memo.count(n)) return memo[n];  
20.   
21.   const lli ln = (lli)ceil(log10(n) / log10(2));  
22.   
23.   lli mn = n - 1;  
24.   for (lli p = 2; p <= ln; ++p) {  
25.     lli x = (lli)floor(pow(n, 1.0 / p));  
26.     lli y = (lli)ceil(pow(n, 1.0 / p));  
27.     lli a = rec(x) + abs(n - lpow(x, p));  
28.     lli b = rec(y) + abs(n - lpow(y, p));  
29.     mn = min(mn, min(a + 1, b + 1));  
30.   }  
31.   
32.   return memo[n] = mn;  
33. }  
34.   
35. class ThePower {  
36. public:  
37.   int count(long long N)  
38.   {  
39.     memo.clear();  
40.     return rec(N);  
41.   }  
42. };  

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);
  }
};