SRM334 div1 medium

#define LIM 3500000

が大事。
3^6+9^6×6=3189375<3500000
なので範囲外アクセスを起こさない。

#include <cstring>
#include <cstdio>

#define LIM 3500000
typedef long long LL;
using namespace std;

LL cache[LIM];

class ExtendedHappyNumbers 
{
	public:

		int K;

		LL S(LL n)
		{
			LL r=0;
			while(n!=0)
			{
				LL a=n%10,b=1;
				for(LL i=0;i<K;i++)
					b*=a;
				r+=b;
				n/=10;
			}
			return r;
		}

		LL rec(LL n)
		{
			LL &r=cache[n];
			if(0<r)
				;
			else if(r==-3)
				r=LIM-1;
			else
			{
				r--;
				r=min(n,rec(S(n)));
			}
			return r;
		}

		LL calcTheSum(int A, int B, int _K) 
		{
			K=_K;
			memset(cache,-1,sizeof(cache));
			LL ans=0;
			for(LL i=1;i<LIM;i++)
				rec(i);

			cout << "calc-end" << endl;
			cout << "S(99)=" << S(99) << endl;

			for(LL i=A;i<=B;i++)
				ans+=cache[i];
			return ans;
		}
};