プロジェクトオイラー問９５ - c21coterie @ ウィキ

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);
}