1. 问题背景与核心挑战最近在整理蓝桥杯历年真题的解题思路翻到了第十届国赛C组的试题E“序列求和”。这道题乍一看很多人会以为又是一道考察基础循环累加的送分题毕竟“序列求和”听起来太常规了。但真正上手去解尤其是想在竞赛的有限时间内拿到满分就会发现里面藏着好几个需要仔细琢磨的“坑”。它本质上是一道融合了数学思维、大数处理、算法优化和边界条件判断的综合题非常能检验一个选手的基本功是否扎实以及面对问题时能否跳出思维定势。题目的大意是给定一个正整数n要求计算从1到n所有整数中每个数各位数字之和的总和。举个例子如果n12那么我们需要计算 1的各位和是12的各位和是2……10的各位和是10111的各位和是11212的各位和是123。 最终结果就是 123456789123 51。最直接的想法当然是从1循环到n对每个数拆解并累加其各位数字。这个方法对于小的n比如几万、几十万是可行的。但蓝桥杯的测试数据规模往往很大n可以轻松达到10^9甚至更大。这时候O(n)的时间复杂度就完全不可接受了程序会超时。这就是这道题的第一个核心挑战必须找到一种远快于线性扫描的数学规律或计算方法。第二个挑战是结果可能非常大。当n很大时这个总和会是一个巨大的整数远超Java中int甚至long类型的表示范围。因此我们必须使用能够处理大整数的类型比如Java的BigInteger。很多初学者在这里会丢分因为他们用long类型存储结果遇到大数据时就会溢出得到错误答案。所以解决这道题的关键不在于写出循环而在于如何摒弃循环通过数学方法直接计算出结果。下面我就来详细拆解这道题的几种解题思路从最容易想到的暴力法到逐步优化最后给出能够应对大规模数据的最优解。2. 暴力解法理解问题与暴露瓶颈在寻找高效解法之前我们先实现一个最朴素的暴力解法。这个过程非常重要它能帮助我们彻底理解题目要求并且通过测试小规模数据来验证我们后续推导出的数学公式是否正确。2.1 暴力解法的实现暴力解法的逻辑非常直接初始化一个BigInteger类型变量sum用于存储总和避免溢出。循环i从1到n。对于每个i计算其各位数字之和。通常的做法是在一个while循环中不断用i % 10取得最低位数字并累加到一个临时变量中然后用i / 10去掉最低位直到i变为0。将每个数的各位和加到总sum中。import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); long n sc.nextLong(); // 注意输入用long接收但计算过程用BigInteger BigInteger totalSum BigInteger.ZERO; for (long i 1; i n; i) { long temp i; int digitSum 0; while (temp 0) { digitSum temp % 10; temp / 10; } totalSum totalSum.add(BigInteger.valueOf(digitSum)); } System.out.println(totalSum); sc.close(); } }2.2 暴力法的局限性分析运行上面的代码当n100,000十万时在我的电脑上已经能感觉到明显的延迟。当n10^7一千万时程序需要运行好几秒。而题目可能的数据范围是10^9以上这个时间开销是完全无法接受的。我们来简单估算一下时间复杂度。对于每个数i计算其各位和需要O(log₁₀ i)的时间因为数字的位数约等于以10为底的对数。所以总的时间复杂度大约是O(n log n)。当n极大时这个复杂度是灾难性的。注意这里有一个常见的编码细节。在计算每个数的各位和时我们使用了long temp i而不是直接操作循环变量i。这是因为循环变量i在循环体中如果被修改i / 10会破坏循环的逻辑导致死循环或者结果错误。这是一个新手容易踩的坑。暴力法虽然低效但它为我们提供了两个重要价值验证工具我们可以用暴力法计算出小规模n比如n10000的准确结果用来验证我们后续推导出的高效算法的正确性。明确优化目标它清晰地告诉我们必须找到一种不依赖于遍历每个数的方法。这引导我们去观察序列求和的数学规律。3. 数学规律挖掘从枚举到公式要摆脱逐个计算的困境我们必须从整体上观察“1到n所有数位和”这个结果。我们可以按数字的每一位来考虑贡献而不是按每一个数来考虑。3.1 按位贡献法原理假设我们计算从1到1234的所有数位和。我们可以分别考虑个位、十位、百位、千位上的数字分别贡献了多少。1. 个位的贡献个位上的数字每10个数0-9, 10-19, ...就会循环一次。从1到1234有多少个完整的“0-9”循环呢1234 / 10 123个完整循环。每个完整循环中个位上的数字0-9各出现一次其和为 012...9 45。 所以完整循环部分的贡献是123 * 45。 那么不完整的部分呢也就是最后一个不完整循环中个位上的数字。1234 % 10 4这意味着最后一个循环中个位上的数字是从0,1,2,...,4。我们需要计算从1到4的和注意当考虑具体数字时是从1开始而不是从0开始因为我们的序列是1到n。所以不完整部分的贡献是1234 10。 因此个位的总贡献是123*45 10。2. 十位的贡献十位上的数字变化周期是10000-99, 100-199, ...。从1到1234有多少个完整的“00-99”循环1234 / 100 12个完整循环。每个完整循环中十位上的数字0-9各出现10次例如在00-99这100个数中十位为0出现了10次00-09为1出现了10次10-19...。所以每个数字的贡献是数字 * 10那么一个完整循环的总贡献是(012...9) * 10 45 * 10 450。 完整循环部分的贡献是12 * 450。 不完整部分1234 % 100 34。这意味着在最后一个不完整循环第13个“百”区间即1200-1234中十位上的数字。我们需要看这个区间内十位数字的规律。十位数字是几取决于这个数在哪个“十”的区间。34 / 10 3所以十位数字完整地走完了0,1,2,3分别对应00-09,10-19,20-29,30-39区间。每个数字出现了10次吗不在最后一个不完整区间里每个十位数字出现的次数需要仔细计算。 实际上更通用的方法是对于不完整部分十位数字为dd从0到currentDigit-1时它出现的次数是一个完整的“个位周期”即10次。当十位数字等于currentDigit时它出现的次数是remainder 1次余数部分1因为从0开始。 在这个例子中currentDigit 334的十位remainder 434的个位。十位为012时各出现10次。贡献为(012)*10 3*10 30? 不对是(012)3, 再乘以10等于30。十位为3时出现了4 1 5次数字30,31,32,33,34。贡献为3 * 5 15。 所以十位不完整部分贡献是30 15 45。 因此十位的总贡献是12*450 45。3. 百位、千位的贡献可以依此类推。百位的周期是1000完整循环数1234/10001每个完整循环贡献45*1004500。不完整部分1234%1000234currentDigit 234/100 2remainder 234%100 34。百位为01时各出现100次。贡献(01)*100 1*100100? 不对(01)1, 乘以100等于100。百位为2时出现了34 1 35次数字200到234。贡献2 * 35 70。 百位总贡献1*4500 (10070) 45001704670。千位的周期是10000完整循环数1234/100000。不完整部分1234%100001234currentDigit 1234/1000 1remainder 1234%1000 234。千位为0出现0次不千位为0意味着数字小于1000在我们的序列1-1234中从1到999千位确实是0但“0”本身不贡献和。所以千位为0的贡献是0。千位为1时出现了234 1 235次数字1000到1234。贡献1 * 235 235。 千位总贡献235。最后把所有位的贡献相加个位(12345105545) 十位(12450455445) 百位(4670) 千位(235) 15895。 我们可以用暴力程序验证n1234时结果是否为15895以此检验我们的规律是否正确。3.2 通用公式推导与算法设计根据上面的分析我们可以总结出一个适用于任意正整数n的算法初始化结果sum 0。初始化基数factor 1表示当前处理的是个位。当n / factor ! 0时循环继续即还有更高位需要处理 a. 计算当前位的“完整循环”部分 *completeCycles n / (factor * 10)。这表示有多少个完整的“0-9”周期。 * 每个完整周期中当前位上的数字0-9各出现了factor次。所以一个完整周期的贡献是(01...9) * factor 45 * factor。 * 完整循环总贡献completePart completeCycles * 45 * factor。 b. 计算当前位的“不完整循环”部分 *remainder n % (factor * 10)。这是最后一个不完整周期内的数字。 *currentDigit (remainder / factor)。这是不完整周期中当前位上的数字可能为0。 * 对于不完整周期当前位上的数字dd从0到currentDigit-1各出现了factor次。这部分贡献为(0 1 ... (currentDigit-1)) * factor (currentDigit - 1) * currentDigit / 2 * factor。 * 对于数字currentDigit它出现的次数是(remainder % factor) 1次因为从当前位为currentDigit的最小值开始计数。这部分贡献为currentDigit * ((remainder % factor) 1)。 * 不完整部分总贡献incompletePart (currentDigit * (currentDigit - 1) / 2) * factor currentDigit * ((remainder % factor) 1)。 c. 将完整部分和不完整部分的贡献加到总结果中sum completePart incompletePart。 d.factor * 10准备处理下一位。循环结束sum即为最终结果。这个算法的时间复杂度是O(log₁₀ n)因为循环次数等于n的位数。对于n10^18long的极限也只需要循环不到20次效率极高。4. 算法实现、边界处理与测试验证理论推导完成后我们需要用代码实现它并仔细处理各种边界情况。4.1 基于数学规律的Java实现import java.math.BigInteger; import java.util.Scanner; public class SequenceSumOptimized { public static void main(String[] args) { Scanner sc new Scanner(System.in); long n sc.nextLong(); // 使用BigInteger存储结果防止溢出 BigInteger sum BigInteger.ZERO; long factor 1; // 从个位开始 while (n / factor ! 0) { // 计算完整循环部分 long completeCycles n / (factor * 10); // 45 * factor 可能超出long范围所以直接用BigInteger计算 BigInteger completePart BigInteger.valueOf(completeCycles) .multiply(BigInteger.valueOf(45)) .multiply(BigInteger.valueOf(factor)); // 计算不完整循环部分 long remainder n % (factor * 10); long currentDigit remainder / factor; long lowerCount remainder % factor; // 第一部分0 到 currentDigit-1 的数字贡献 // 求和公式 (currentDigit - 1) * currentDigit / 2 BigInteger firstPart BigInteger.ZERO; if (currentDigit 0) { // 注意0到currentDigit-1的和是 (currentDigit-1)*currentDigit/2 // 但currentDigit可能为0此时这部分和为0 long sumZeroToCurrentMinusOne (currentDigit - 1) * currentDigit / 2; firstPart BigInteger.valueOf(sumZeroToCurrentMinusOne) .multiply(BigInteger.valueOf(factor)); } // 第二部分数字currentDigit的贡献 // 出现次数是 lowerCount 1 BigInteger secondPart BigInteger.valueOf(currentDigit) .multiply(BigInteger.valueOf(lowerCount 1)); // 合并不完整部分贡献 BigInteger incompletePart firstPart.add(secondPart); // 累加到总结果 sum sum.add(completePart).add(incompletePart); // 处理下一位 factor * 10; } System.out.println(sum); sc.close(); } }4.2 关键边界条件与细节剖析在实现过程中有几个细节必须小心处理否则极易出错数据类型与溢出这是本题最大的陷阱。即使输入n在long范围内910^18中间计算结果completeCycles * 45 * factor也可能远远超出long的表示范围约910^18。例如当n接近10^18factor为10^17时completeCycles约为1045*factor约为4.510^18乘积就达到4.510^19远超long范围。因此必须使用BigInteger进行所有累加和乘法运算。在上面的代码中我们一上来就将completeCycles转换为BigInteger再进行乘法确保了计算安全。不完整部分中currentDigit为0的情况当currentDigit为0时公式(currentDigit - 1) * currentDigit / 2仍然成立结果为0但为了代码清晰和安全我显式地判断了if (currentDigit 0)。实际上当currentDigit0时firstPart的计算公式(0-1)*0/2在数学上等于0但在编程中直接计算(-1)*0/2也是0不会出错。不过显式判断是一个好习惯。lowerCount的含义lowerCount remainder % factor它表示在当前位确定为currentDigit时更低位的数字范围。例如处理十位时factor10remainder34currentDigit3lowerCount4。这意味着在十位为3的这个分组里个位可以从0取到4共5个数30,31,32,33,34。所以currentDigit出现的次数是lowerCount 1。循环终止条件while (n / factor ! 0)确保了只要n在当前factor位上还有数字即n factor就继续循环。当factor大于n时n/factor等于0循环结束。4.3 测试验证与对拍为了确保算法的正确性我们必须进行充分的测试。小数据验证用暴力算法和优化算法同时计算n1, 10, 99, 123, 1234等值对比结果是否一致。这是最基本的验证。特殊值测试n0题目通常要求正整数n但可以测试边界。我们的算法中while循环条件0/10不进入循环结果为0符合预期。n9只有个位且是完整循环的末尾。completeCycles0,remainder9,currentDigit9,lowerCount0。计算得sum45正确。n10个位completeCycles1,remainder0,currentDigit0... 计算后个位贡献45。十位completeCycles0,remainder10,currentDigit1,lowerCount0。十位贡献1。总贡献46。验证1到10的各位和1,2,3,4,5,6,7,8,9,1总和为46。正确。大数据压力测试可以用优化算法计算n10^9, 10^12等大数虽然无法用暴力法验证但可以检查结果是否在合理范围内例如数量级是否正确并且程序是否能在毫秒级返回结果。对于竞赛题通常官方会提供一些测试点我们可以用已知答案来验证。一个实用的调试技巧在开发过程中可以写一个“对拍”程序。即同时运行暴力程序数据范围调小比如n10000和优化程序用脚本随机生成成千上万个n比较两个程序的输出是否一致。这是确保算法正确性非常有效的方法。5. 性能对比与算法选择思考让我们直观感受一下两种方法的效率差异。假设n 1,000,000,000 (10^9)。暴力法需要循环10^9次每次循环内部还有一个位数的循环平均约5次操作。总操作数约5*10^9次。在普通的计算机上这可能需要数分钟甚至更久在竞赛的1秒或2秒时间限制下必然超时。数学公式法n的位数是10所以外层while循环只执行10次。每次循环内部是常数次的基本运算加减乘除和取模。总操作数在几十次左右执行时间可以忽略不计远小于1毫秒。这种性能差距是数量级上的碾压。这也正是算法竞赛的魅力所在——找到问题的本质用巧劲代替蛮力。在解决这类“序列求和”问题时我们可以总结出一个通用的思维模式识别问题规模首先看数据范围。如果n很大比如超过10^7线性算法基本没戏必须找规律。尝试枚举观察从小规模数据n1,2,3,...,20开始手动或写程序计算结果观察数列是否有规律。对于数位问题按位贡献是一个非常高频且有效的切入点。推导通用公式将观察到的规律用数学语言描述出来并考虑所有边界情况如首位、末位、进位等。注意数据溢出在公式推导过程中就要预估中间结果和最终结果的大小选择合适的数-据类型int,long,BigInteger。编写健壮代码实现公式时特别注意循环条件、下标、整除和取模运算确保逻辑正确。回到这道蓝桥杯真题它完美地考察了选手是否具备这种思维转换能力。很多人在考场上卡在暴力法超时就是因为没有跳出“逐个计算”的惯性思维。而一旦掌握了按位贡献的思想这道题就从一个编程题变成了一个数学推导题代码实现反而变得简单。最后关于BigInteger的使用虽然它比原生类型慢但在这道题中由于计算次数极少O(log n)次其开销完全可以接受。在真正的竞赛中如果时间卡得极其严格且结果在long范围内也可以尝试用long进行所有计算但必须非常小心地处理乘法溢出可能需要使用Math.multiplyExact或手动判断这反而增加了复杂度。因此对于不确定范围的情况直接使用BigInteger是更稳妥、更清晰的选择。