「プロジェクトオイラー問７４」の編集履歴（バックアップ）一覧はこちら

「プロジェクトオイラー問７４」(2014/03/02 (日) 06:00:25) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

http://projecteuler.net/problem=74

*Problem 74 「桁の階乗による連鎖」 †
145は各桁の階乗の和が145と自分自身に一致することで有名である.

1! + 4! + 5! = 1 + 24 + 120 = 145

169の性質はあまり知られていない. これは169に戻る数の中で最長の列を成す. このように他の数を経て自分自身に戻るループは3つしか存在しない.

169 → 363601 → 1454 → 169
871 → 45361 → 871
872 → 45362 → 872

どのような数からスタートしてもループに入ることが示せる.

例を見てみよう.

69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)

69から始めた場合, 列は5つの循環しない項を持つ. また100万未満の数から始めた場合最長の循環しない項は60個であることが知られている.

100万未満の数から開始する列の中で, 60個の循環しない項を持つものはいくつあるか?

解法
７ケタが全部9でも２５４万程度で、8桁になっても２８０万程度です。
つまり多めに見積もっても２６０万程度までをメモ化しておけばよいと分かります。
これで十分間に合います。



 #include<stdio.h>
 #include<string.h>
 
 char lens[2600000];
 const int fact[10]={1,1,2,6,24,120,720,5040,40320,362880};
 
 int toNextNum(int num){
 	int re=0;
 	while(num!=0){
 		re+=fact[num%10];
 		num/=10;
 	}
 	return re;
 }
  
 int search(int num){
 	if(num==toNextNum(num)){
 		lens[num]=0;
 		return 0;
  	}
 	if(lens[num]>=0){
 		return lens[num];
 	}else{
  		lens[num]=0;
 		lens[num]=search(toNextNum(num))+1;
 		if(lens[num]>60)lens[num]=60;
 		return lens[num];
 	}
 } 
 
 int main(){
 	int ans=0;
 	memset(lens,-1,sizeof(lens));
 	for(int i=1;i<1000000;i++){
  		if(lens[i]>=0){
 			ans+=(lens[i]>=60);
 		}else{
 			ans+=(search(i)>=60);
 		}
 	}
 	printf("%d\n",ans);
 }

http://projecteuler.net/problem=74

*Problem 74 「桁の階乗による連鎖」 †
145は各桁の階乗の和が145と自分自身に一致することで有名である.

1! + 4! + 5! = 1 + 24 + 120 = 145

169の性質はあまり知られていない. これは169に戻る数の中で最長の列を成す. このように他の数を経て自分自身に戻るループは3つしか存在しない.

169 → 363601 → 1454 → 169
871 → 45361 → 871
872 → 45362 → 872

どのような数からスタートしてもループに入ることが示せる.

例を見てみよう.

69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)

69から始めた場合, 列は5つの循環しない項を持つ. また100万未満の数から始めた場合最長の循環しない項は60個であることが知られている.

100万未満の数から開始する列の中で, 60個の循環しない項を持つものはいくつあるか?

解法
７ケタが全部9でも２５４万程度で、8桁になっても２８０万程度です。
つまり多めに見積もっても２６０万程度までをメモ化しておけばよいと分かります。
これで十分間に合います。
今回もＣ++でＰｒｏｌｏｇではありません。


 #include<stdio.h>
 #include<string.h>
 
 char lens[2600000];
 const int fact[10]={1,1,2,6,24,120,720,5040,40320,362880};
 
 int toNextNum(int num){
 	int re=0;
 	while(num!=0){
 		re+=fact[num%10];
 		num/=10;
 	}
 	return re;
 }
  
 int search(int num){
 	if(num==toNextNum(num)){
 		lens[num]=0;
 		return 0;
  	}
 	if(lens[num]>=0){
 		return lens[num];
 	}else{
  		lens[num]=0;
 		lens[num]=search(toNextNum(num))+1;
 		if(lens[num]>60)lens[num]=60;
 		return lens[num];
 	}
 } 
 
 int main(){
 	int ans=0;
 	memset(lens,-1,sizeof(lens));
 	for(int i=1;i<1000000;i++){
  		if(lens[i]>=0){
 			ans+=(lens[i]>=60);
 		}else{
 			ans+=(search(i)>=60);
 		}
 	}
 	printf("%d\n",ans);
 }