数列求和-加强版(C语言)

题目详情
给定某数字A（1≤A≤9）以及非负整数N（0≤N≤100000），求数列之和S=A+AA+AAA+⋯+AA⋯A（N个A）。例如A=1, N=3时，S=1+11+111=123。

要求
时间限制: 200 ms
内存限制: 64 MB
代码长度限制: 16 KB

输入格式：
输入数字A与非负整数N。

输出格式：
输出其N项数列之和S的值

输入样例：
1 3

输出样例：
123

个人思路
这道题的局限是当输出其N项之和S的值时发现S太大了，
拿最大的来说:当A=9,N=100000时，
S肯定是>最后一项999…9(总共有10^5个9)>9.0e+99999

int(最大为2.0e+31 - 1)还是long long(最大为2.0e+63 - 1)还是long double(最大为1.1e+4932)都不可以满足大于9.0e+99999

所以我打算采用竖式加法计算,这样可以把很大的一个S这样的数分成各个位数的值来存储，可以用一个数组记录各个位数的数值，而十进制中各个位数上的值又不可能超过10,所以避免了越界问题。可以先从低位到高位如此分位计算和分别考虑前一位的进位问题,然后再用数组元素来记录下各个位数上的数值。

不用动态链表或者可变数组的话需要考虑一开始定义数组的大小,而决定数组大小的又是当其N项数列之和S的值的最大值(也就是当A=9,N=100000时),此时的最大的数S是可以估算出来的,可以用下面方法:

• 我们知道9,99,999 …999999 的通项公式为an=10^n-1,
  则1,11,111 的通项公式为(10^n-1)/9 ,
  所以m,mm,mmm 的通项公式为m*(10^n-1)/9 （1≤m≤9）;
  接下来用等比数列的求和方法Sn=a1(1-q^n)/(1-q)可以估算出最大的数S。
  求出来大概是总共有100002-1=100001位(参考下图计算结果)
  
  所以最高位是第100001位,所以数组大小只需定义为int s[100001]={0}即可。

• 下面代码有相应的注释

#include <stdio.h>
//int在正数的范围是1~2147483647
int main(int argc,char const *argv[])
{
	int A,N;
	int s[100001]={0};		//记录结果的各个位数，通过计算当A=9,N=100000时,最多为100001个位数 
	scanf("%d %d",&A,&N);
	int jinwei=0,num=N,weishu=0;  	//num来辅助各个位数的计算   ,  weishu用来判断输出时的有效最高位 
							//接下来进行竖式加法计算 
	for(int i=0; i<N+1 ;i++)//i=0表示从个位开始相加 ,且最多到N+1位(i的值最多为N)
	{
		s[i]=num*A+jinwei;			//这步的最大值为9*100000=900000<2147483647,往前面的位数只能比该数小,所以这步不会越界 
		jinwei=s[i]/10;				//下一位需要进位多少
		s[i]=s[i]%10;				//该位数上最后是与10的余数 
		num--;						//为更高位的计算做准备 
	}
	
	for(int i=N; i>=0 ;i--)//用来判断输出时的有效最高位(筛选作用) 
	{
		if(s[i]!=0)
		{
			weishu=i;
			break;
		}
	}
	
	for(int i=weishu; i>=0 ;i--)//从有效的最高位开始逐个输出
	{
		printf("%d",s[i]);
	}
	
	return 0;
}