A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.

For example,

44  32  13  10  1  1 85  89  145  42  20  4  16  37  58  89

Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.

How many starting numbers below ten million will arrive at 89?

题目大意:

通过将一个数各位的平方不断相加，直到遇到已经出现过的数字，可以形成一个数字链。

例如：

44  32  13  10  1  1 85  89  145  42  20  4  16  37  58  89

因此任何到达1或89的数字链都会陷入无限循环。令人惊奇的是，以任何数字开始，最终都会到达1或89。

以一千万以下的数字n开始，有多少个n会到达89？

算法一：常规方法，从2~10000000逐个判断，同时统计结果

#include
     
         #define N 10000000int fun(int n){    int t, sum;    sum = 0;     while(n) {        t = n % 10;        sum += t * t;        n /= 10;    }    return sum;}void solve(void){    int i, sum, t;    sum = 0;    for(i = 2; i < N; i++) {        t = fun(i);        while(1) {            if(t == 89) {                sum++;                break;            } else if(t == 1) {                break;            } else {                t = fun(t);            }        }    }    printf("%d\n",sum);}int main(void){    solve();    return 0;}
     

算法二（优化）：使用一个bool型数组，保存每次结果，由于最大的中间数为9999999产生的：9^2*7 = 567，所以bool型数组的大小开到600足够

#include 
     
      #include 
      
             #define N 10000000bool a[600] = {
   false};int fun(int n){    int t, sum;    sum = 0;     while(n) {        t = n % 10;        sum += t * t;        n /= 10;    }    return sum;}void solve(void){    int i, sum, t, temp;    sum = 0;    for(i = 2; i < N; i++) {        t = fun(i);        temp = t;        if(a[temp]) {            sum++;        } else {            while(1) {                t = fun(t);                if(a[t] || t == 89) {                    a[temp] = true;                    sum++;                    break;                } else if(t == 1) {                    break;                } else {                }            }        }    }    printf("%d\n",sum);}int main(void){    solve();    return 0;}
      
     

Answer:

8581146