一道ACM题目（AdAndy的作业)，来帮帮忙啊解决办法

一道ACM题目（AdAndy的作业)，来帮帮忙啊。
Problem Description
Andy每天都有很多作业要做，他的老师总是在说“这些作业你明天必须交上来……”。现在他找你帮忙做其中的一项作业，给出N个整数A1, A2, ..., AN，有 M 个询问 q (L, R)，对于每个询问，你要输出一个整数，第L个数到第R个数的乘积，这个乘积不会超过1000位。

 Input
输入包含多组测试数据。每组数据第一行为两个整数N，M (N <= 800, M <= 1000) 接下来N行，给出这N个整数。然后M行，每行两个整数L R表示一个询问。

 Output
对于每个询问，输出相应的结果。当所有询问结束之后输出“Homework Finished”。

 Sample Input
10 5
9
7
9
6
4
9
5
8
3
4
5 9
3 8
8 10
10 10
1 7
1 1
1
1 1
 Sample Output
4320
77760
96
4
612360
Homework Finished
1
Homework Finished


/****************************************************************/
我的程序:

C/C++ code

#include<iostream>using namespace std;char *s=new char[1001];char *ss=new char[1001];char *p1=new char[1001];int len_a,len_b,cont_a,cont_b,num,length,int_a,int_b,temp1,temp2,i;void mul(char *a,char *b){    num = 0;    len_a=strlen(a)-1;    len_b=strlen(b)-1;    length=len_a+len_b;        temp2=i=0;    while(1)    {        cont_a=cont_b=temp1=0;        if(num<=len_b)cont_a=0;        else cont_a=num-len_b;        if(num>len_b) cont_b=len_b;        else cont_b=num;        while(cont_b>=0&&cont_a<=len_a)        {            int_a=*(a+cont_a)-48;            int_b=*(b+cont_b)-48;            cont_a ++;            cont_b --;            temp1+=int_a*int_b;        }                *(s+i)=(temp1+temp2)%10+48; i++;        temp2=(temp1+temp2)/10;        num ++;        if(num>length)        {            if(temp2!=0) {*(s+i)=temp2+48;*(s+i+1)='\0';}            else {*(s+i)='\0';break;}        }        }}int main(){    int n,m,an[801],am1,am2,tmp;    register int i,j;    char *p;    while(scanf("%d%d",&n,&m)!=EOF)    {        for(i=1;i<=n;i++)            scanf("%d",&an[i]);        for(i=0;i<m;i++)        {            scanf("%d%d",&am1,&am2);            tmp=am2-am1;            sprintf(ss,"%d",an[am1]);            for(j=1;j<=tmp;j++)            {                sprintf(p1,"%d",an[am1+j]);                mul(ss,strrev(p1));                strcpy(ss,s);            }            p=strrev(s);            printf("%s\n",p);        }        printf("Homework Finished\n");    }    delete s;    delete ss;    delete p1;    return 0;}

我是用大数乘法来做的, 但是TLE了,
我的大数乘法的大致算法是:
比如12 * 34
把它们转为字符串并倒序,为"21"和"43"
然后;
10的0次方位为:2*4=8
10的1次方位为:1*4+2*3=10, 向2次方进位后变0
10的2次方位为:1*3=3 加上前面的进位为:3+1=4
把它们组合起来得到字符串"804"
再把该字符串倒序变408即12 * 34的结果.....
这样做TLE了, 谁有更好的解决办法...Orz

[解决办法]
建议发到算法区
[解决办法]
有几个优化，建议你试试：
1：乘法的进制建开大一些，如10^8，这样大于10^9才向前进位。每位保存的是一个8位数，速度会快很多。而且不用字符串，而用整型数组。
2：你可以写一个大整型的除法，先把从第一位到第N位的结果都保存起来，这样可以简化乘法为一个大数与一个小数相乘。这样就每次查询就不用每次都进行了整个区间相乘。可以求p-q的就可以变为p / (q-1)
[解决办法]
改用unsigned int[]数组，每个数组元素的取值范围为0~2^32-1。比用一个char代表一个10进制位要快很多。运算的原理都是一样的。
正负号单独处理。
[解决办法]
当然你也可以建线段树省掉高精度除法的麻烦.
[解决办法]
http://hi.baidu.com/ckh_0330/blog/item/22df51086075fcc53ac76351.html