题目描述在传统的“长乘法”中我们通过将xxx与yyy的各个数字从个位开始相乘来确定两个整数xxx和yyy的乘积。这些乘法的结果按适当的方式排列并相加得到最终的乘积。这种运算的表示通常以特定方式进行。例如计算123×95123 \times 95123×95123 95 --- 615 1107 --- 11685被乘数xxx和乘数yyy各占一行后面跟一条水平线。然后将yyy的每一位与xxx相乘的结果显示在单独的行上后面再跟一条水平线最后是最终乘积。在本题中你需要执行一系列这样的乘法并以这种传统格式显示结果。输入格式输入数据的每一行最后一行除外包含两个整数xxx和yyy由空白字符分隔。每个整数不超过101010位数字。输入数据的最后一行只包含一个0表示输入结束。输出格式对于每一对整数即除最后一行外的每一行以如上所示的形式输出乘法结果。每个乘法输出后跟一个空行。如果乘数yyy是一位数或x0x0x0则中间结果只有一行此时省略第二条水平线和中间行直接输出乘积。第一条水平线的连字符数量应等于max(∣x∣,∣y∣)\max(|x|, |y|)max(∣x∣,∣y∣)的位数。第二条水平线的连字符数量如果产生应等于乘积的位数。只输出有效的数字前导零不显示。样例输入4 7 135 46 12345 862 0 123456789 0样例输出4 7 -- 28 135 46 --- 810 540 --- 6210 12345 862 ----- 24690 74070 98760 ----- 10641390 123456789 0 --------- 0题目分析问题的本质这是一个格式化输出问题。需要按照传统长乘法的竖式格式输出两个整数的乘法过程。长乘法的步骤输入两个整数xxx和yyy如果y0y0y0或x0x0x0直接输出乘积为000如果yyy只有一位则直接输出乘积省略中间行否则输出xxx右对齐输出yyy右对齐输出一条水平线连字符数量 max(∣x∣,∣y∣)\max(|x|, |y|)max(∣x∣,∣y∣)对于yyy的每一位从个位到最高位计算x×该位x \times \text{该位}x×该位并在右侧补相应数量的000输出右对齐如果有多行中间结果输出第二条水平线连字符数量 乘积的位数输出乘积格式细节所有数字右对齐第一条水平线的长度 max(∣x∣,∣y∣)\max(|x|, |y|)max(∣x∣,∣y∣)第二条水平线的长度 乘积的位数中间结果中乘以000的项应被省略不显示如果中间结果只有一行则省略第二条水平线参考代码// Long Multiplication// UVa ID: 338// Verdict: Accepted// Submission Date: 2016-07-05// UVa Run Time: 0.090s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 高精度乘法返回乘积的字符串表示stringmultiplication(longlongx,longlongy){if(x0||y0)return0;// 如果两个数都在 9 位以内直接用 64 位整数计算安全if(x999999999y999999999)returnto_string(x*y);// 否则模拟竖式乘法vectorstringlines;for(intrightSpace0;y0;y/10,rightSpace){longlongtempx*(y%10);// x 乘以当前位的数字string zzto_string(temp)string(rightSpace,0);// 补零reverse(zz.begin(),zz.end());// 反转以便从低位相加lines.push_back(zz);}// 逐位相加string z;intcarry0;for(inti0;ilines.back().length();i){intsum0;for(intj0;jlines.size();j)if(ilines[j].length())sumlines[j][i]-0;sumcarry;carrysum/10;z.push_back(sum%100);}// 处理最高位进位if(carry0)z.push_back(carry0);// 反转回正常顺序reverse(z.begin(),z.end());// 去除前导零while(z.front()0)z.erase(z.begin());returnz;}intmain(intargc,char*argv[]){ios::sync_with_stdio(false);longlongx,y;string z;while(cinxy){if(x0y0)break;// 输入结束标志zmultiplication(x,y);// 计算乘积// 确定最大宽度intmaxXYLengthmax(to_string(x).length(),to_string(y).length());intmaxLengthmax((int)(z.length()),maxXYLength);// 输出第一行被乘数coutsetw(maxLength)rightxendl;// 输出第二行乘数coutsetw(maxLength)rightyendl;// 输出第一条水平线coutsetw(maxLength)rightstring(maxXYLength,-)endl;// 如果乘数是一位数或乘数为 0直接输出乘积if(y9||x0){coutsetw(maxLength)rightzendl;}else{// 收集中间结果排除乘以 0 的项vectorpairint,stringlines;longlongtempYy;for(intrightSpace0;tempY0;tempY/10,rightSpace){longlongtempx*(tempY%10);if(temp0)continue;// 乘以 0 的项不显示lines.push_back(make_pair(rightSpace,to_string(temp)));}// 如果有多行中间结果输出它们if(lines.size()1){for(autoline:lines)coutsetw(maxLength-line.first)rightline.secondendl;// 输出第二条水平线coutsetw(maxLength)rightstring(z.length(),-)endl;}// 输出乘积coutzendl;}coutendl;// 每个测试用例后空行}return0;}
UVa 338 Long Multiplication
题目描述在传统的“长乘法”中我们通过将xxx与yyy的各个数字从个位开始相乘来确定两个整数xxx和yyy的乘积。这些乘法的结果按适当的方式排列并相加得到最终的乘积。这种运算的表示通常以特定方式进行。例如计算123×95123 \times 95123×95123 95 --- 615 1107 --- 11685被乘数xxx和乘数yyy各占一行后面跟一条水平线。然后将yyy的每一位与xxx相乘的结果显示在单独的行上后面再跟一条水平线最后是最终乘积。在本题中你需要执行一系列这样的乘法并以这种传统格式显示结果。输入格式输入数据的每一行最后一行除外包含两个整数xxx和yyy由空白字符分隔。每个整数不超过101010位数字。输入数据的最后一行只包含一个0表示输入结束。输出格式对于每一对整数即除最后一行外的每一行以如上所示的形式输出乘法结果。每个乘法输出后跟一个空行。如果乘数yyy是一位数或x0x0x0则中间结果只有一行此时省略第二条水平线和中间行直接输出乘积。第一条水平线的连字符数量应等于max(∣x∣,∣y∣)\max(|x|, |y|)max(∣x∣,∣y∣)的位数。第二条水平线的连字符数量如果产生应等于乘积的位数。只输出有效的数字前导零不显示。样例输入4 7 135 46 12345 862 0 123456789 0样例输出4 7 -- 28 135 46 --- 810 540 --- 6210 12345 862 ----- 24690 74070 98760 ----- 10641390 123456789 0 --------- 0题目分析问题的本质这是一个格式化输出问题。需要按照传统长乘法的竖式格式输出两个整数的乘法过程。长乘法的步骤输入两个整数xxx和yyy如果y0y0y0或x0x0x0直接输出乘积为000如果yyy只有一位则直接输出乘积省略中间行否则输出xxx右对齐输出yyy右对齐输出一条水平线连字符数量 max(∣x∣,∣y∣)\max(|x|, |y|)max(∣x∣,∣y∣)对于yyy的每一位从个位到最高位计算x×该位x \times \text{该位}x×该位并在右侧补相应数量的000输出右对齐如果有多行中间结果输出第二条水平线连字符数量 乘积的位数输出乘积格式细节所有数字右对齐第一条水平线的长度 max(∣x∣,∣y∣)\max(|x|, |y|)max(∣x∣,∣y∣)第二条水平线的长度 乘积的位数中间结果中乘以000的项应被省略不显示如果中间结果只有一行则省略第二条水平线参考代码// Long Multiplication// UVa ID: 338// Verdict: Accepted// Submission Date: 2016-07-05// UVa Run Time: 0.090s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 高精度乘法返回乘积的字符串表示stringmultiplication(longlongx,longlongy){if(x0||y0)return0;// 如果两个数都在 9 位以内直接用 64 位整数计算安全if(x999999999y999999999)returnto_string(x*y);// 否则模拟竖式乘法vectorstringlines;for(intrightSpace0;y0;y/10,rightSpace){longlongtempx*(y%10);// x 乘以当前位的数字string zzto_string(temp)string(rightSpace,0);// 补零reverse(zz.begin(),zz.end());// 反转以便从低位相加lines.push_back(zz);}// 逐位相加string z;intcarry0;for(inti0;ilines.back().length();i){intsum0;for(intj0;jlines.size();j)if(ilines[j].length())sumlines[j][i]-0;sumcarry;carrysum/10;z.push_back(sum%100);}// 处理最高位进位if(carry0)z.push_back(carry0);// 反转回正常顺序reverse(z.begin(),z.end());// 去除前导零while(z.front()0)z.erase(z.begin());returnz;}intmain(intargc,char*argv[]){ios::sync_with_stdio(false);longlongx,y;string z;while(cinxy){if(x0y0)break;// 输入结束标志zmultiplication(x,y);// 计算乘积// 确定最大宽度intmaxXYLengthmax(to_string(x).length(),to_string(y).length());intmaxLengthmax((int)(z.length()),maxXYLength);// 输出第一行被乘数coutsetw(maxLength)rightxendl;// 输出第二行乘数coutsetw(maxLength)rightyendl;// 输出第一条水平线coutsetw(maxLength)rightstring(maxXYLength,-)endl;// 如果乘数是一位数或乘数为 0直接输出乘积if(y9||x0){coutsetw(maxLength)rightzendl;}else{// 收集中间结果排除乘以 0 的项vectorpairint,stringlines;longlongtempYy;for(intrightSpace0;tempY0;tempY/10,rightSpace){longlongtempx*(tempY%10);if(temp0)continue;// 乘以 0 的项不显示lines.push_back(make_pair(rightSpace,to_string(temp)));}// 如果有多行中间结果输出它们if(lines.size()1){for(autoline:lines)coutsetw(maxLength-line.first)rightline.secondendl;// 输出第二条水平线coutsetw(maxLength)rightstring(z.length(),-)endl;}// 输出乘积coutzendl;}coutendl;// 每个测试用例后空行}return0;}
