Project Euler 92

各桁の2乗を足し合わせて新たな数を作ることを、同じ数が現れるまで繰り返す。

例えば

　　44 → 32 → 13 → 10 → 1 → 1
　　85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

のような列である。どちらも1か89で無限ループに陥っている。
驚くことに、どの数から始めても最終的に1か89に到達する。

では、10,000,000より小さい数で89に到達する数はいくつあるか。

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

#include <iostream>
#include <deque>
using namespace std;

// xを各桁ごとにばらしてdequeに挿入する。
deque<int> integerDigits(int x){
	deque<int> arr;
	while(x!=0){
		arr.push_front(x%10);
		x/=10;
	}
	return arr;
}

int sumSquareDigit(int n){
	int ans=0;
	deque<int> dn = integerDigits(n);

	for(int i=0 ; i<dn.size() ; i++){
		ans+=dn[i]*dn[i];
	}
	return ans;
}

int check[10000000];

int main(){

	for(int i=0 ; i<10000000 ; i++){
		check[i] = 0;
	}

	int cnt = 0;
	for(int i=1 ; i<10000000 ; i++){
		//if(i%10000==0) cout << i << endl;
		int tmp = i;

		while(1){
			tmp = sumSquareDigit(tmp);
			if(check[tmp]==-1 || tmp==1){
				check[i] = -1;				
				break;
			}
			if(check[tmp]==1 || tmp==89){
				cnt++;
				check[i] = 1;
				break;
			}
		}
	}
	cout << cnt << endl;

	int end;
	cin >> end;
}

10分位で適当に。計算時間的にはボツ。