The number 145 is well known for the property that the sum of the factorial of its digits is equal to 145:
1! + 4! + 5! = 1 + 24 + 120 = 145
Perhaps less well known is 169, in that it produces the longest chain of numbers that link back to 169; it turns out that there are only three such loops that exist:
169 363601
1454
169 871
45361
871 872
45362
872
It is not difficult to prove that EVERY starting number will eventually get stuck in a loop. For example,
69 363600
1454
169
363601 (
1454) 78
45360
871
45361 (
871) 540
145 (
145)
Starting with 69 produces a chain of five non-repeating terms, but the longest non-repeating chain with a starting number below one million is sixty terms.
How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?
题目大意：
数字145有一个著名的性质：其所有位上数字的阶乘和等于它本身。
1! + 4! + 5! = 1 + 24 + 120 = 145
169不像145那么有名，但是169可以产生最长的能够连接回它自己的数字链。事实证明一共有三条这样的链：
169 363601
1454
169 871
45361
871 872
45362
872
不难证明每一个数字最终都将陷入一个循环。例如：
69 363600
1454
169
363601 (
1454) 78
45360
871
45361 (
871) 540
145 (
145)
从69开始可以产生一条有5个不重复元素的链，但是以一百万以下的数开始，能够产生的最长的不重复链包含60个项。
一共有多少条以一百万以下的数开始的链包含60个不重复项？
//（Problem 74）Digit factorial chains
// Completed on Tue, 18 Feb 2014, 04:21
// Language: C11
//
// 版权所有（C）acutus (mail: acutus@126.com)
// 博客地址：http://www.cnblogs.com/acutus/
#include<stdio.h>
#include<math.h>
#include<stdbool.h> #define N 1000000
long long fac[]; //保存1~ 9阶乘的数组 long long factorial(int n) //计算阶乘函数
{
if(n == || n == ) return ;
else return n * factorial(n - );
} void init() //初始化数组
{
int i;
for(i = ; i <= ; i++) {
fac[i] = factorial(i);
}
} long long sum(long long n) //计算整数n各位的阶乘的和
{
int ans = ;
while(n) {
ans += fac[n % ];
n /= ;
}
return ans;
} bool fun(int n)
{
int i, count, t;
bool flag = false;
count = ;
while() {
switch(n) {
case : count += ; flag = true; break;
case : count += ; flag = true; break;
case : count += ; flag = true; break;
case : count += ; flag = true; break;
case : count += ; flag = true; break;
case : count += ; flag = true; break;
case : count += ; flag = true; break;
default: t = sum(n);
if( n == t) {
flag = true;
break;
} else{
n = t;
count++; break;
}
}
if(flag) break;
}
if(count == ) return true;
else return false;
} void solve()
{
int i, count;
count = ;
for(i = ; i <= N; i++) {
if(fun(i)) count++;
}
printf("%d\n", count);
} int main()
{
init();
solve();
return ;
}
|
Answer:
|
402 |