UVa 568 - Just the Facts

// UVa 568 - Just the Facts

#include <iostream>
#include <stdio.h>
using namespace std;

struct triad {
	int twos, fives, digit;
};

int main() {
	triad f[10001];
	f[1].twos = 0;
	f[1].fives = 0;
	f[1].digit = 1;
	for (int i = 2; i <= 10000; i++) {
		int j = i;
		int c2 = 0;
		while (j % 2 == 0) {
			c2++;
			j = j / 2;
		}
		int c5 = 0;
		while (j % 5 == 0) {
			c5++;
			j = j / 5;
		}
		int dig = j % 10;
		f[i].twos = f[i - 1].twos + c2;
		f[i].fives = f[i - 1].fives + c5;
		f[i].digit = (f[i - 1].digit * dig) % 10;
		int mn = min(f[i].twos, f[i].fives);
		f[i].twos -= mn;
		f[i].fives -= mn;
	}

	int n;
	int p2[4] = { 6, 2, 4, 8 };
	while (cin >> n) {
		int dig = f[n].digit;
		if (f[n].fives)
			dig *= 5;
		else if (f[n].twos)
			dig *= p2[f[n].twos % 4];
		printf("%5d -> %d\n", n, dig % 10);
	}

	return 0;
}