PTA基础编程题目集 7-38数列求和-加强版（C++语言实现）

摘要：本文是PTA编程题"数列求和-加强版"的题解，涵盖题目描述、输入输出格式及C++语言实现，展示核心算法：高精度大整数加法（数组存储+进位处理）、按位统计每一位上A出现的次数。

题目描述

给定某数字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。

输入格式：

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

输出格式：

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

输入样例：

1 3

输出样例：

123

解题思路

核心问题分析

本题需要解决的核心问题：

1. 数据规模大：N最大为100000，结果可达10万位以上，无法用普通整型存储
2. 按位计算思想：模拟竖式加法，统计每一位上A出现的次数
3. 进位处理：逐位计算后处理进位，最后输出

算法原理说明

观察数列结构：

A = A * 1 AA = A * 11 AAA = A * 111 ... + AA...A(N个) = A * 111...1(N个)

从个位（第1位）到第N位分析：

• 第i位（从右往左数，i从1到N）：有i个数在这一位上有A（只有前i项的第i位是A）
• 因此第i位的和 =i * A + 来自低位的进位
• 当前位数字 =sum % 10
• 新的进位 =sum / 10

具体计算步骤

1. 处理边界：N=0时直接输出0
2. 初始化数组result[100001]存储结果各位，carry=0
3. 从i=N到i=1逆向遍历（从最高位到最低位？不，这里i表示该位有i个A相加，实际上数组下标i对应第i位）
   • sum = i * A + carry
   • result[i] = sum % 10
   • carry = sum / 10
4. 遍历结束后若carry>0，result[0]存进位
5. 根据是否有进位决定从result[0]还是result[1]开始输出

代码流程说明

1. main函数-输入与边界处理（第29-36行）

• 输入a和n
• n==0时直接输出0返回

2. main函数-初始化（第38-39行）

• result数组初始化为0，大小100001
• carry进位初始化为0

3. main函数-按位求和循环（第41-45行）

• 从i=n到i=1循环
• 每位和 = i*a + carry（第i位有i个a相加）
• result[i] = sum % 10（存当前位）
• carry = sum / 10（更新进位）

4. main函数-进位与输出（第47-57行）

• 若carry>0：最高位有进位，存入result[0]，从result[0]到result[n]输出
• 否则：从result[1]到result[n]输出
• 末尾输出换行

代码流程图

解题流程图

代码部分实现

#include<iostream>usingnamespacestd;intmain(){inta,n;cin>>a>>n;if(n==0){cout<<"0"<<endl;return0;}intresult[100001]={0};intcarry=0;for(inti=n;i>=1;i--){intsum=i*a+carry;result[i]=sum%10;carry=sum/10;}if(carry>0){result[0]=carry;for(inti=0;i<=n;i++){cout<<result[i];}}else{for(inti=1;i<=n;i++){cout<<result[i];}}cout<<endl;return0;}