杭电ACM 1163题老是超时啊。求大牛优化。http:⼀⼀acm.hdu.edu.cn⼀showproblem.php?pid=1163

#include
#include
#include
typedef __int64 lld;
const int BIT=1000000000;
const int MAXLEN=4500;
struct BigNum
{
int dig[MAXLEN];
int len;
void clr()
{
memset(dig,0,sizeof(dig));
len=1;
}
}ZERO;
BigNum multi(BigNum a,BigNum b)
{
BigNum c=ZERO;
int i,k,j;
lld t;
c.len=a.len+b.len;
if(c.len>MAXLEN)return c;
for(i=0;i for(j=0;j {
t=(lld)a.dig[i]*(lld)b.dig[j];
if(t>=BIT)
{
c.dig[i+j]+=t%BIT;
c.dig[i+j+1]+=t/BIT;
}
else
{
c.dig[i+j]+=t;
}
k=i+j;
while(c.dig[k]>=BIT)
{
c.dig[k+1]+=c.dig[k]/BIT;
c.dig[k]%=BIT;
k++;
}

}
if(c.dig[c.len-1]==0)c.len--;
return c;
}
int digsum(int n)
{
int ret=0;
while(n>0)
{
ret+=n%10;
n/=10;
}
return ret;
}
int main()
{
//我是先写这个高精度代码,看出规律的,有循环,高精度代码要超时.可能是我的高精度不够好吧,有nlogn的乘法的,我不会.要用博利叶变换
int n,sum=0,x,i,j;
BigNum tmp,ans;
ZERO.clr();
int zz[18]={1 ,4 ,9 ,4 ,2 ,9 ,7 ,1 ,9 ,1 ,5 ,9 ,4 ,7 ,9 ,7 ,8 ,9};
while(scanf("%d",&n)!=EOF&&n>0)
//for(j=1;j<50;j++)
{
printf("%d\n",zz[(n-1)%18]);
continue;
n=j;
//printf("%d:",n);
tmp=ZERO;
tmp.dig[0]=n;
ans=ZERO;
ans.dig[0]++;
while(n)
{
if(n&1)ans=multi(ans,tmp);
tmp=multi(tmp,tmp);
n>>=1;
}
sum=0;
for(i=0;i while(sum>9)
{
x=0;
while(sum>0)
{
x+=sum%10;
sum/=10;
}
sum=x;
}
printf("%d ",sum);

}
return 0;
}
/*
1 4 9 4 2 9 7 1 9 1 5 9 4 7 9 7 8 9
1 4 9 4 2 9 7 1 9 1 5 9 4 7 9 7 8 9
1 4 9 4 2 9 8 7 9 1 5 9 7 请按任意键继续. . .

*/

求数字根的推导证明，看懂了就能做出来了。
证：
引理：一个数除以9的余数等于它的数字和除以九的余数
设正整数a的“根”为c
则a mod 9 = c mod 9
因为c < 10
所以当c mod 9 > 0时，c = c mod 9
当c mod 9 = 0时，c = 9
因为a mod 9 = c mod 9
所以当a mod 9 > 0时，c = a mod 9
当a mod 9 = 0时，c = 9
完毕