下午做了后才正式接触了九余定理，不过这题可不是用的九余定理做的。网上的博客千篇一律，所以本篇就不发篇幅过多介绍九余定理了；

   但还是要知道什么是九余定理：

   九余数定理

  一个数对九取余后的结果称为九余数。

  一个数的各位数字之和相加后得到的<10的数字称为这个数的九余数（如果相加结果大于9，则继续各位相加）

   简单的说就是：一个整数模9的结果与这个整数的各位数字之和模9的结果相同；

  以前做题不知道有这个定理一般暴力就过了，求数位和也不复杂，只不过更省时间而已；

  先来看看HDU-1163,博主是在NYOJ上做的这题时间限制是3s；

  题意：求N^N的数位和（结果是个位数），开始打表找规律也没发现什么规律，于是想了另外一种方法：可以发现n的数位和的n次方再求数位和其实就等于n的n次方的数位和；比如：n=11,结果应该是5；11的数位和等于2，而2^11的数位和就等于5；进一步发现：

F(2^11)=F(8*8*8*4)=F(8*8)*F(8)*F(4)=F(64)*F(8)*F(4)=F(10)*F(8)*F(4)=F(80)*F(4)=F(8)*F(4)=F(32)=F(5)=5;

F(11^11)=F(11)*F(11)*...*F(11)=F(2)*F(2)*...*F(2)=F(2)^11=F(2^11);

    所以此题就可以先求出N的数位和然后只需一层循环一直乘以N的数位和，注意当乘积大于10时需要再进行求数位和然后再重复操作；最后别忘了将循环里得到的值再求数位和；

#include
    
     using namespace std;int main(){    int n,i;    while(~scanf("%d",&n)&&n)    {        int sum=n;        while(sum>=10)//将n的数位和求出；        {            int x=0;            while(sum)            {                x+=sum%10;                sum/=10;            }            sum=x;        }        int d=sum;        for(i=2; i<=n; i++)        {            while(sum>=10)            {                int x=0;                while(sum)                {                    x+=sum%10;                    sum/=10;                }                sum=x;            }            sum*=d;        }        while(sum>=10)//最后得到的值再求数位和；        {            int x=0;            while(sum)            {                x+=sum%10;                sum/=10;            }            sum=x;        }        printf("%d\n",sum);    }    return 0;}
    

 上述代码在NYOJ上运行时间是1680ms,时限3s；而HDU运行时间0ms,时限1s,真是神奇呵!;

 运用九余定理AC代码：确实很简洁方便！

#include
    
     using namespace std;int main(){    int n,temp;    while(~scanf("%d",&n)&&n)    {        temp=n;        for(int i=2;i<=n;i++)            temp=(temp%9*n)%9;        if(temp==0)//此处需要注意；            printf("9\n");        else            printf("%d\n",temp%9);    }    return 0;}
    

 

   下面再来看,此题题意很简单，就是求A*B的数位和；很明显方法很多，但是时限是1s，所以。。。所以这题只能用九余定理做吗？应该是的，我用九余定理运行时间986ms勉强过了，而用分治法超时了。。。

#include
    
     using namespace std;int main(){    int t;    long long n,m;    scanf("%d",&t);    while(t--)    {        scanf("%lld%lld",&n,&m);        if(m==0||n==0)//这里需注意一下特殊情况；        {            printf("0\n");            continue;        }        n%=9;        m%=9;        long long x=(n*m)%9;        if(x==0)            printf("9\n");        else            printf("%lld\n",x);    }    return 0;}