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(,&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(,mul);scanf(,&n);}return 0;}
解题报告：代码来自百度搜索，下面是本人的代码，运行后发现效率太低了，完全可以判断为超时，再三思考下决定参考代码
TLEMyCode
#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));, &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(, 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;
人的一生是奋斗的一生，人们为了取得成功都在不断地努力着，
