SRM 437 D2 1000 ThePower

#include <ctime>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
using namespace std;
typedef long long LL;
#define FOR(k,a,b) for(int k(a); k < (b); ++k)
#define REP(k,a) for(int k=0; k < (a); ++k)

class ThePower {
    int cacheS;
    vector<LL> cache;
    LL INF;
    LL mSqrt(LL a, double r)
    {
        return (LL) pow((double) a,1.0/r );
    }
    LL mPow(LL a, int i)
    {
        if(i==1) return a;
        LL tmp=a*mPow(a,i-1);
        return (tmp>a)?tmp:INF;
    }
    int calc(LL n)
    {
        if(n<cacheS && cache[n]!=-1)
            return cache[n];
        LL res=n-1;
        FOR(i,2,70)
        {
            LL tmp=mSqrt(n,i);
            FOR(j,-50,50)
                if(tmp+j>0)
                {
                    LL ttmp=mPow(tmp+j,i);
                    if (ttmp==INF)
                        continue;
                    ttmp-=n;
                    if(ttmp<0)
                        ttmp*=-1;
                    if(res>1+ttmp)
                        res=min(res,1+ttmp+calc(tmp+j));
                }
        }
        if(n<cacheS)
            cache[n]=res;
        return res;
    }
public:

    int count(LL n)
    {
        INF=1000000000000LL;
        cacheS=1000000;
        cache.resize(cacheS,-1);
        return calc(n);
    }
};