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

「プロジェクトオイラー問９５」(2014/03/04 (火) 12:33:39) の最新版変更点

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

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

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2095


*Problem 95 「友愛鎖」 †
ある数の真の約数とは, それ自身を除く約数すべてである. 例えば, 28 の真の約数は 1, 2, 4, 7, 14 である. これらの約数の和は 28 に等しいため, これを完全数と呼ぶ.

面白いことに, 220 の真の約数の和は 284 で, 284 の真の約数の和は 220 となっており, 二つの数が鎖をなしている. このため, 220 と 284 は友愛数と呼ばれる.

さらに長い鎖はあまり知られていないだろう. 例えば, 12496 から始めると, 5 つの数の鎖をなす.

12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → ...)
この鎖は出発点に戻っているため, 友愛鎖と呼ばれる.

いずれの要素も 1,000,000 を超えない最長の友愛鎖の最小のメンバーを求めよ.



解法
約数の和はエラトステネスの篩もどきで１００万までをメモ化しておきます。
後は鎖をたどりますが、鎖の和になってるところだけを検出する探索を行います。
一度探索したところはＢＡＤ定数で蓋をして計算量を稼ぎます。

 #include<stdio.h>
 #include<string.h> 
 
 const int LIMIT = 1000*1000;
 const int BAD=-2;
 int yakusuSum[LIMIT+1]={0};
 int chain[LIMIT+1];
 int tempLen,tempMin;
 bool isChain=false;
  
 int search(int num,int deep){
 	if(num>LIMIT || chain[num]==BAD){
  		isChain=false;
		return BAD;
 	}
 	if(0<=chain[num]){
 		tempLen=deep-chain[num]-1;
 		tempMin=num;
 		isChain=true;
 		return tempLen;
  	}else{
 		chain[num]=deep;
 		int re=search(yakusuSum[num],deep+1);
 		if(re>=0&&tempMin>num)tempMin=num;
 		chain[num]=BAD;
 		return re-1;
 	}
 } 
 
 
 int main(){
 	int ansLen=0,ansMin=1000*1000;
 	memset(chain,-1,sizeof(chain));
 	for(int i=1;i*2<=LIMIT;i++){
 		for(int j=i*2;j<=LIMIT;j+=i){
 			yakusuSum[j]+=i;
 		}
 	}
 	for(int i=1;i<=LIMIT;i++){
 		search(i,0);
  		if(isChain==false)continue;
 		if(tempLen>ansLen){
 			ansMin=tempMin;
 			ansLen=tempLen;
 		}else if(tempLen==ansLen&&ansMin>tempMin){
 			ansMin=tempMin;
 		}
 	}
 	printf("%d %d",ansMin,ansLen);
 }