HDU1163【九余数定理】【水题】

eddy

题目大意：给你一个正整数n，把n的各位上数字加起来，假设结果小于10，则所得结果为n的数字根，假设大于10，则再把上边所得结果各位上的数字加起来。如今给你一个数n，求n^n的数字根

思路：一看数据规模10000^10000，肯定要把n拆分掉。通过找规律发现，求n^n的数字根可转化为先求n的数

字根a，然后求a*n的原根，赋给a，接着依次求a*n,求n-1次，就得到了n^n的数字根。

比如：求5^5的数字

第一种方法：5^5 = 3125     3 + 1 + 2 + 5 = 11      1 + 1 = 2   终于结果是2

另外一种方法：5的数字根是5   5*5*5*5*5 =  25*5*5*5   

   相当于25的数字根7 *5*5*5  = 35*5*5 = 8*5*5 = 40*5 = 4*5 = 20 = 2

   终于结果为2

对于另外一种方法能够用九余数定理，更加简单。

九余数定理：一个数N各位数字的和，对9取余等于这个数对9取余

<span style="font-family:Microsoft YaHei;font-size:18px;">//不使用九余数定理
#include<stdio.h>

int main()
{
    int n;
    while(~scanf("%d", &n) && n)
    {
        int a = n;
        int b = 0;
        while(a > 0)
        {
            b += a % 10;
            a /= 10;
        }
        if(b != 0)
            a = b;
        int x = a;
        for(int i = 1; i < n; i++)
        {
            a *= x;
            b = 0;
            while(a > 0)
            {
                b += a % 10;
                a /= 10;
            }
            if(b != 0)
                a = b;
        }
        b = 0;
        while(a > 0)
        {
            b += a % 10;
            a /= 10;
        }
        if(b != 0)
            a = b;
        printf("%d\n",a);
    }
    return 0;
}
</span>

//使用九余数定理
#include <stdio.h>

int main()
{
    int n,a,sum,i;
    while(scanf("%d",&n)&&n)
    {
        sum=1;
        for(i=0;i<n;i++)
        {
            sum=sum*n%9;
        }
        if(sum==0)
             printf("9\n");
        else
             printf("%d\n",sum);
        
    }
    return 0;
}