diff options
author | Iru Cai <mytbk920423@gmail.com> | 2018-06-03 21:49:08 +0800 |
---|---|---|
committer | Iru Cai <mytbk920423@gmail.com> | 2018-06-03 22:31:26 +0800 |
commit | 7f25c6fc31b376ca1ed0f4c183ef4d232b6ee2b5 (patch) | |
tree | d3da22b57962d387aeec51cdba9eea240ba504c6 /euler74.c | |
parent | 90ab4dafa14d811ed0d7d1466675a69036be5392 (diff) | |
download | project_euler-7f25c6fc31b376ca1ed0f4c183ef4d232b6ee2b5.tar.xz |
73,74,85,357
Diffstat (limited to 'euler74.c')
-rw-r--r-- | euler74.c | 57 |
1 files changed, 57 insertions, 0 deletions
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 <stdio.h> +#include <string.h> + +#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); +} |