HDU ACM 1163 Eddy's digital Roots

Eddy's digital Roots

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 2730 Accepted Submission(s): 1572

Problem Description

The digital root of a positive integer is found by summing the digits of the integer. If the resulting value is a single digit then that digit is the digital root. If the resulting value contains two or more digits, those digits are summed and the process is repeated. This is continued as long as necessary to obtain a single digit.
For example, consider the positive integer 24. Adding the 2 and the 4 yields a value of 6. Since 6 is a single digit, 6 is the digital root of 24. Now consider the positive integer 39. Adding the 3 and the 9 yields 12. Since 12 is not a single digit, the process must be repeated. Adding the 1 and the 2 yeilds 3, a single digit and also the digital root of 39.
The Eddy's easy problem is that : give you the n,want you to find the n^n's digital Roots.

Input

The input file will contain a list of positive integers n, one per line. The end of the input will be indicated by an integer value of zero. Notice:For each integer in the input n(n<10000).

Output

Output n^n's digital root on a separate line of the output.

Sample Input

2

4

0

Sample Output

4

4

Author

eddy

Recommend

JGShining

#include<stdio.h>
int main()
{
    int n,mul,num,i;
    scanf("%d",&n);
    while(n)
    {
        num=n;
        n=n%9;
        mul=1;
        for(i=1;i<=num;i++)
            mul=(mul*n)%9;
        mul=(mul==0?9:mul);
        printf("%d\n",mul);
        scanf("%d",&n);
    }
               return 0;
}

解题报告：
代码来自百度搜索，下面是本人的代码，运行后发现效率太低了，完全可以判断为超时，再三思考下决定参考代码

TLE MyCode

#include<stdio.h>
#include<string.h>
int sum[40020];
int main()
{
    int  i, j, t, loop, temp, e, flag, len, n;
    memset(sum, 0, sizeof(sum));
    while(scanf("%d", &n) != EOF && n)
    {
        flag = 0;
        sum[0] = 1;
        for(i=n; i>=1; --i)
        {
            for(j=0, e=0; j<40020; ++j)
                {
                    temp = sum[j];
                    sum[j] = (e + sum[j]*n)%10;
                    e = (e + temp*n)/10; 
                }
        }
        for(i=40019; i>=0; --i)   flag += sum[i];
        temp = flag;
        e = 0;
        if(temp >= 10)
        while(temp/10 != 0)
        {
            e += temp%10;
            temp = temp/10;
            if(temp/10 == 0)
            {
                e += temp%10;
                if(e/10 != 0) {temp = e; e = 0;}
                else break;
            } 
        }
        else e = temp;
        printf("%d\n", e);
        memset(sum, 0, sizeof(sum));
    }
    return 0;
    
}

在看Discuss时，发现提示对9的求模！！不解，搜索百度后找注释，都是只发现对9求模的关键字，发现和题目无关系，思索了一会儿，我大概发现了题目的运算说明和代码思路（对9求模）的关系：
假设一个数是：A=an x 10^n + a(n-1) x 10^(n-1) + …… + a1 x 10^1 + a0, 按照题目的意思是将A的A次方相乘后将各位的位数相加，相加后判断是否<10，否的话继续将各位的位数相加，如此循环直到最后相加的数0< result <=9范围内，这里先从相反的方向思考(算是事后诸葛亮吧，但总比没弄清楚好），设A的A次方相乘后的值为M，则M和A一样，也可以写成M=bn x 10^n + b(n-1) x 10^(n-1) + …… + b1 x 10^1 + b0，也可以这样写:M=bn x ((10^n-1)+1) + b(n-1) x ((10^(n-1)-1)+1) + …… + b1 x ((10^1)-1)+1 + b0，即除了个位上的数外其余位数上的数都可以用bn=999…（（n-1）个9）+ 1表示，除去括号得：

M=（bn x 9999…+ bn) + (b(n-1) x 999…+b(n-1)+ b1 x 9 + b1 + b0;

题目条件表述说将各位上的数相加，对于上式来说即为将各位位数上的数乘上权值后对9的求模再相加（999…都能被9整除），得到的就是M1=bn+ b(n-1)+…+b1+b0（先不要想着将这一堆数按十进制进行相加，应想着这些数都是求模后剩下来的，等下还是要求模的）, 相加的数M1如果>=10，根据题目条件的意思又会继续循环相加，直至得到的Mn<10 此时Mn就为result（所需求的数）　　　　　　　　　　　　　　　　　　——上面所说的都是为了说明题目这样讲述是为了对９求模而由此得到余数

回到最初的M， M是由A个A相乘后的结果，此时须明白这样的一个式子：(n*n)mod(x)可以写成((n%x)*(n%x))%x，而M=A*A，再结合代码就能够理解为什么有n个n%9相乘再求模了（n%9得到的数总让人以为是Ａ个位上的数！！而事实上不是）