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

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2074
Problem 74 「桁の階乗による連鎖」 †
各桁の数の階乗和に関する問題。

解法
ループになるケースは他の数を経由する循環は３つしかないと問題に明記されているのでそれを利用します。
残りは自分自身と同じ数になる数だけです。
後はメモ化で適当に計算速度を稼ぐだけです。

#include<stdio.h>

const int LIMIT=1000*1000;
int memo[LIMIT]={0};

int fact[10];

int set_fact(int n){
	if(n==0){
		fact[0]=1;
		return 1;
	}else{
		fact[n]=set_fact(n-1)*n;
		return fact[n];
	}
} 

int calc(int n){
	int re=0;
	while(n>0){
		re+=fact[n%10];
		n/=10;
	}
	return re;
}
 
int saiki(int n){
	if(n<LIMIT&&memo[n]>0){
		return memo[n];
	}else{
		int n2=calc(n);
		if(n2==n)return 1;
		int Len=saiki(n2)+1;
 		if(n<LIMIT){
			memo[n]=Len;
		}
		return Len;
	}
}

int main(){
 	memo[169]=memo[363601]=memo[1454]=3;
	memo[871]=memo[45361]=2;
	memo[872]=memo[45362]=2;
	set_fact(9);
	int ans=0;
	for(int i=2;i<LIMIT;i++){
 		if(saiki(i)==60){
			ans++;
		}
	}
	printf("%d",ans);
}