下午做了NYOJ-424Eddy's digital Roots后才正式接触了九余定理，不过这题可不是用的九余定理做的。网上的博客千篇一律，所以本篇就不发篇幅过多介绍九余定理了；
但还是要知道什么是九余定理：
九余数定理
一个数对九取余后的结果称为九余数。
一个数的各位数字之和相加后得到的<10的数字称为这个数的九余数（如果相加结果大于9，则继续各位相加）
简单的说就是：一个整数模9的结果与这个整数的各位数字之和模9的结果相同；
以前做题不知道有这个定理一般暴力就过了，求数位和也不复杂，只不过更省时间而已；
先来看看HDU-1163Eddy's digital Roots,博主是在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<bits/stdc++.h>
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<bits/stdc++.h>
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;
}
下面再来看NYOJ-485A*B Problem,此题题意很简单，就是求A*B的数位和；很明显方法很多，但是时限是1s，所以。。。所以这题只能用九余定理做吗？应该是的，我用九余定理运行时间986ms勉强过了，而用分治法超时了。。。
#include<bits/stdc++.h>
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;
}