From 7f25c6fc31b376ca1ed0f4c183ef4d232b6ee2b5 Mon Sep 17 00:00:00 2001 From: Iru Cai Date: Sun, 3 Jun 2018 21:49:08 +0800 Subject: 73,74,85,357 --- euler74.c | 57 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 57 insertions(+) create mode 100644 euler74.c (limited to 'euler74.c') diff --git a/euler74.c b/euler74.c new file mode 100644 index 0000000..a0020f6 --- /dev/null +++ b/euler74.c @@ -0,0 +1,57 @@ +#include +#include + +#define MAXTERM 3000000 +int next[MAXTERM]; + +const int factorial[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880}; + +int sum_fact_digits(int n) +{ + int sum = 0; + while (n > 0) { + sum += factorial[n%10]; + n /= 10; + } + return sum; +} + +void init() +{ + memset(next, 0, sizeof(next)); + for (int i = 1; i < 1000000; i++) { + if (next[i]) + continue; + next[i] = sum_fact_digits(i); + for (int j = next[i]; next[j] == 0; j = next[j]) { + next[j] = sum_fact_digits(j); + } + } +} + +int chainlen(int n) +{ + int chain[100], L = 0; + + while (1) { + for (int i = 0; i < L; i++) { + if (chain[i] == n) + return L; + } + chain[L] = n; + L++; + n = next[n]; + } +} + +int main() +{ + int count = 0; + + init(); + for (int i = 1; i <= 1000000; i++) { + if (chainlen(i) == 60) + count++; + } + printf("%d\n", count); +} -- cgit v1.2.3