プロジェクトオイラー問297 - sinapusu2002 @ ウィキ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20297
フィボナッチ数列の集合の部分和で自然数ｎを現した時、最小の個数の数でｎを現せたときの個数をf(n)とする。
0<n<10＾17Σf(n)
を求めよ。
パキパキと10＾17までの数をcalc関数で割っていって
一度計算したものはmemoしておけばそれで終了です。

試行錯誤時間15分
コード実装時間10分。
計算時間1秒
このへんは難しい問題が多いですがこの問題は非常に簡単でした。
こういう簡単な問題ばかりだといいのですが。

#include<stdio.h>
#include<math.h>
#include<set>
#include<iostream>
#include<map>

const __int64 LA=pow(10,8);
const __int64 LB=pow(10,9);
const __int64 LIMIT=LA*LB;
std::set<__int64> fib;
std::map<__int64,__int64> memo;

__int64 cc=10000;
__int64 calc(__int64 left,__int64 right){
	if(left==1&&right==1)return 1;
	if(left==1&&right==2)return 2;
	std::set<__int64>::iterator it=fib.upper_bound(right);
	it--;
	__int64 c=(*it);
	__int64 a;
	if(memo.size()==cc){
		cc+=10000;
		std::cout<<memo.size();
	}
	
	if(memo.find(c-1)==memo.end()){
		a=calc(1,c-1);
		memo[c-1]=a;
	}else{
		a=memo[c-1];
	}
	__int64 res;
	if(c==right){
		res= a+1;
	}else{
		__int64 b;
		if(memo.find(right-c)==memo.end()){ 
			b=calc(1,right-c);
		}else{
			b=memo[right-c];
		}
		res=a+(right-c)+b+1;
	}
	return res;
} 
 
int main(){
	
	__int64 a=1;
	__int64 b=2;
	fib.insert(a);
	fib.insert(b);
	while(a+b<LIMIT){
		__int64 c=a+b;
		fib.insert(c);
		a=b;
		b=c;
	}
	std::cout<<calc(1,LIMIT-1);
}