UVa 424 Integer Inquiry

题目描述

题目要求计算多个大整数的和。输入包含最多100100100行，每行一个非负整数（可能非常大，长度不超过100100100位），以单独一行的一个000表示输入结束。输出这些整数的总和。

输入格式

输入包含若干行，每行一个由数字组成的字符串，表示一个非负整数。最后一行是一个单独的000，表示输入结束。

输出格式

输出一行，即所有输入整数的和。

样例

输入

123456789012345678901234567890 123456789012345678901234567890 123456789012345678901234567890 0

输出

370370367037037036703703703670

题目分析

本题的核心是实现大整数加法。由于每个整数最多有100100100位，直接使用内置整数类型（如long long最多约191919位）无法存储，需要手动模拟竖式加法过程。

加法模拟

大整数加法从最低位（个位）开始逐位相加，并处理进位。具体步骤：

1. 将两个加数按字符串形式存储，从末位向首位遍历。
2. 对应位相加，加上上一位的进位，得到当前位的和。
3. 当前位的数字为和模101010，进位为和除以101010。
4. 处理完所有位后，若仍有进位，则在最高位添加进位。

多整数求和

对于多个大整数相加，可以依次将每个数累加到一个结果变量中。结果变量也以字符串（或整数数组）形式存储，初始为000。每读入一个新数，将其与当前结果相加，更新结果。

实现细节

• 使用vector<int>或string存储结果，注意低位在数组前端还是后端的选择。常见做法是低位存储在索引000处，这样进位扩展时只需在末尾追加。
• 参考代码中使用了固定长度的字符数组result（长度为110110110），从末尾开始向前存储，这样可以避免反转字符串。但需要注意输出时跳过前导零。

边界情况

• 输入可能只有一个000，此时应输出000。
• 输入的数字可能包含前导零（如00123），但通常输入不会这样。如有前导零，加法结果应正确处理。

复杂度分析

每加一个数的时间复杂度为O(max⁡(len(result),len(num)))O(\max(\text{len}(\text{result}), \text{len}(\text{num})))O(max(len(result),len(num)))，总复杂度O(总数×最大长度)O(\text{总数} \times \text{最大长度})O(总数×最大长度)，完全可接受。

代码实现

// Integer Inquiry// UVa ID: 424// Verdict: Accepted// Submission Date: 2016-07-13// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){ios::sync_with_stdio(false);string line,result=string(110,0);while(getline(cin,line),line!="0"){intdigit=0,carry=0;intj=result.length()-1;for(inti=line.length()-1;i>=0;i--,j--){digit=line[i]-'0'+result[j]+carry;result[j]=digit%10;carry=digit/10;}while(j>=0){digit=result[j]+carry;result[j]=digit%10;carry=digit/10;j--;}}for(inti=0;i<result.length();i++){if(result[i]==0)continue;for(intj=i;j<result.length();j++)cout<<(char)(result[j]+'0');break;}cout<<endl;return0;}