pe92.cpp

// pe92.cpp: определяет точку входа для консольного приложения.
//

// на хаскеле это
// print $ length $ filter (==89) $ map end [1..10000000]
//     where end x = if (r == 89 || r == 1) then r else (end r)
//			where r = sum $ map (^2) $ map digitToInt $ show x

#include "stdafx.h"

char* rs;

int iter(int n) {
	if (n == 89 || n == 1) return n;
	if (rs[n-1] == 0) {
		char* buf = new char[10];
		sprintf(buf, "%i", n);
		int sum = 0;
		for (int i = 0; buf[i] != '\0'; i++) {
			sum += (buf[i] - '0') * (buf[i] - '0');
		}
		return sum;
	} else {
		return rs[n-1];
	}
}

int end(int n) {
	int cur = n;
	do {
		//printf("%i -> ", cur);
		cur = iter(cur);
	} while ((cur != 89) && (cur != 1));
	rs[n-1] = cur;
	//printf("%i\n", cur);
	return cur;
}

int _tmain(int argc, _TCHAR* argv[])
{
	rs = new char[10000001];

	memset(rs, 0, 10000001);
	
	int count = 0;

	for (int i = 1; i <= 10000000; i++) {
		rs[i-1] = end(i); 
		if (i % 100000 == 0) printf("%i -> %i\n", i, rs[i-1]);
		if (rs[i-1] == 89) count++;
	}
	
	printf("The answer is %i.\n", count);
	delete rs;
	getchar();
	return 0;
}