7-38 数列求和-加强版

给定某数字$A(1\le A\le 9)$以及非负整数$N(0\le N\le 100000)$，求数列之和$S=A+AA+AAA+\cdots +AA\cdots A$（$N$个$A$）。例如$A=1,N=3$时，$S=1+11+111=123$。

输入格式

输入数字$A$与非负整数$N$。

输出格式

输出其$N$项数列之和$S$的值。

输入样例

1 3

输出样例

123

分析与答案

非负整数$N(0\le N\le 100000)$意味着连数列的子项都没法用一般的数据类型来储存，更不用说数列和了。和前面的大数计算题目类似，可以用一个足够大的数组来储存结果，每一位对应结果中的一位数字。解决了储存问题还要解决时间问题，对给每一位加上对应的元素然后进位的方法复杂度是$O(n^2)$（每一次循环都要遍历一遍），对于这题这么大的$N$而言很有可能运行超时。对数列和进行分析，可以发现如果不对结果进行进位操作，结果中的第$N$位是$A$，第$N-1$位是$2A$，第$N-2$位是$3A$……以此类推，可以知道如果不执行进位，数组的第i+1位（数组下标从0开始）必定是(n-i)*a。如果先按照这个规律对每一位进行运算和进位，复杂度就可以降到$O(n)$。

最终结果的位数也可以进行估算：数字$A$最大取到9，$9+99+\cdots +99\cdots 9（N\mathrm{个}9）$必然小于$10+100+\cdots +10\cdots 0(N\mathrm{个}0)$，而后者是$N+1$位，所以函数只需要建立一个n+1位大的动态数组即可完整地储存结果（最终结果可能是n位的也可能是n+1位的）。

当然了，如果输入的$N$​是0，那直接输出一个0就可以了。

整个程序的思路如下：

1. 读取输入的a和n，分别对应题目的$A$和$N$​;
2. 如果n==0，直接输出0，结束程序；
3. 建立n+1位的动态数组，采用calloc函数可以同时完成地址分配和初始化；
4. 开始对每一位进行操作，先加上第i+1位对应的a*(n-i)，之所以是加而不是赋值，是因为此时处理的位置可能已经包含前一位进位带来的数值，即便前一位没有进位，calloc已经完成了初始化，使用加操作也不会带来混乱。
5. 如果加上后该位数字已经超过9（>=10），那就要进行进位操作。
6. 完成循环后，局部变量i位于结果从右往左数的第n+1位，如果此时这一位为0，说明结果只有n位，把i往前移，如果不为0则结果有n+1位，保留不动。
7. 从i的位置开始向前循环输出，直到第一个元素为止。

int main(){
   int a = 0,n = 0;
   int i = 0,j = 0;
   scanf("%d %d",&a,&n);
   if(n==0){
      printf("0");
      return 0;
   }
   int *res = (int*)calloc(n+1,sizeof(int));   
   for(i=0;i<n;i++){
      //对于第（i+1）位，a被加了（n-i）次
      *(res+i)+=a*(n-i);
       if(*(res+i)>=10){
         *(res+(i+1))=*(res+i)/10;
         *(res+i)=*(res+i)%10;
      }
   }
   if(*(res+n)==0){
      i=n-1;
   }   
   else
      i=n;
   for(;i>=0;i--)
      printf("%d",*(res+i));
   return 0;
}