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

摘要本文是PTA编程题数列求和-加强版的题解涵盖题目描述、输入输出格式及C语言实现展示核心算法高精度大整数加法数组存储进位处理、按位统计每一位上A出现的次数。题目描述给定某数字A1≤A≤9以及非负整数N0≤N≤100000求数列之和SAAAAAA⋯AA⋯AN个A。例如A1, N3时S111111123。输入格式输入数字A与非负整数N。输出格式输出其N项数列之和S的值。输入样例1 3输出样例123解题思路核心问题分析本题需要解决的核心问题数据规模大N最大为100000结果可达10万位以上无法用普通整型存储按位计算思想模拟竖式加法统计每一位上A出现的次数进位处理逐位计算后处理进位最后输出算法原理说明观察数列结构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具体计算步骤处理边界N0时直接输出0初始化数组result[100001]存储结果各位carry0从iN到i1逆向遍历从最高位到最低位不这里i表示该位有i个A相加实际上数组下标i对应第i位sum i * A carryresult[i] sum % 10carry sum / 10遍历结束后若carry0result[0]存进位根据是否有进位决定从result[0]还是result[1]开始输出代码流程说明1. main函数-输入与边界处理第29-36行输入a和nn0时直接输出0返回2. main函数-初始化第38-39行result数组初始化为0大小100001carry进位初始化为03. main函数-按位求和循环第41-45行从in到i1循环每位和 i*a carry第i位有i个a相加result[i] sum % 10存当前位carry sum / 10更新进位4. main函数-进位与输出第47-57行若carry0最高位有进位存入result[0]从result[0]到result[n]输出否则从result[1]到result[n]输出末尾输出换行代码流程图是否是否开始输入数字a和项数nn等于0?输出0并结束初始化结果数组和进位0i从n到1逆向遍历当前位和等于i乘a加进位当前位存和的个位进位更新为和的十位及以上i减1遍历完成进位大于0?最高位存入进位从最高位进位开始输出从第一位开始输出输出换行结束解题流程图是否理解数列求和问题分析数据规模需高精度存储观察按位规律第i位有i个A相加确定数组存储方案首位存可能进位设计按位计算流程当前位和进位处理N等于0边界情况编写核心循环处理最高位进位编写输出逻辑用小数据验证A等于1N等于3得123结果正确?考虑大数测试场景检查位序进位输出起点完成代码部分实现#includeiostreamusingnamespacestd;intmain(){inta,n;cinan;if(n0){cout0endl;return0;}intresult[100001]{0};intcarry0;for(intin;i1;i--){intsumi*acarry;result[i]sum%10;carrysum/10;}if(carry0){result[0]carry;for(inti0;in;i){coutresult[i];}}else{for(inti1;in;i){coutresult[i];}}coutendl;return0;}