5-38 数列求和-加强版 (20分)

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

输入格式：

输入数字AA与非负整数NN。

输出格式：

输出其NN项数列之和SS的值。

输入样例：

1 3
输出样例：

123

思路用：这么大的数用long long都会溢出的，用数组存储每位数，满十就进位加一。

C语言代码：

#include <stdio.h>
#define size 100001
int main(void)
{
    int arr[size];
    int num, n;
    scanf("%d %d", &num, &n);
    
    int i, j;
    for (i=1; i<n+1; i++){
        // arr[0] 存储个位数， arr[1] 十位数……arr[n] n^10位数 
        for (j=0; j<i; j++){
            arr[j] += num;
            // 如果满十就进一
            if (arr[j] > 9){
                arr[j] = arr[j] % 10;
                arr[j+1] = arr[j+1]+1;
            }
        }
    }
    
    // 高位先打印 
    for (i=n-1; i>=0; i--){
        printf("%d", arr[i]);
    }
    
    return 0;
}

有两个测试用例没有通过，一个超时， 一个答案错误，待解决。

QQ截图20170724152100.jpg

• 答案错误是因为没有考虑 数字 A = 0 的情况
  修正的部分代码：

    // 高位先打印 
    int flag = 0;
    for (i=n; i>=0; i--){
        if(arr[i] != 0){    // 因为可能存在进位， 所以 n 位可能是1 可能是0 
            flag = 1;
        }
        if (flag==1 || i==0){   // 如果 num = 0， 数组元素会全为0，输出末尾的零 
            printf("%d", arr[i]);
        }
    }

修改1.jpg

暂时还不知道怎么优化……