Eddy's digital Roots
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 5161 Accepted Submission(s): 2883
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.
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
240
Sample Output
44
九余数法，也叫弃九法，可以用来求一个数的弃九数，也能叫“根数”（即求这个数所有位的数的和，如果不是10以内的数，就重复这个过程，直到变成10以内的数，比如128的结果就是2，首先把128中的1,2,8相加得到11，再把11的1,1相加得2），求弃九数的方法就是拿这个数对9取模，若为0则弃九数是9，否则为余数。
更进一步可以用来验算加减运算是否正确，比如1863+716=2579，首先1863的弃九数为9,716弃九数为5,2579弃九数为4，因为（9+5）%9=4，所以加法运算很可能正确（注意！仅仅是很可能！正确概率约为8/9），再如3413-2546=867，依次计算出三者弃九数分别为2,8,3，即验算2-8=3，因为2小于8，所以要验算这个（2+9）-8=3，得出结论：运算很可能正确。顺带一提，乘积的弃九数等于弃九数的乘积的弃九数。比如123*45*82的结果453873的弃九数为9，三者的弃九数6、9、9的乘积486的弃九数为9。
九余数法用到了数论中的一个性质：任意一个非零的n进制整数mod（n-1）后的数根与原数的数根相同。
这道题由于n不大，所以一般方法也能过，但也能用快速幂。
#include<cstdio>//非快速幂代码int main(){ int n; while(scanf("%d",&n)!=EOF&&n) { int ans=1,cnt=n; while(cnt--) { ans*=n; ans%=9; } printf("%d\n",ans?ans:9); } return 0;}#include<cstdio>//快速幂代码int fastmod(int b,int c,int mod){ int re=1,base=b; while(c) { if(c&1) re=((re%mod)*(base%mod))%mod; base=((base%mod)*(base%mod))%mod; c>>=1; } return re;}int main(){ int n; while(scanf("%d",&n)!=EOF&&n) { int ans=fastmod(n,n,9); printf("%d\n",ans?ans:9); } return 0;}版权声明：本文为博主原创文章，未经博主允许不得转载。