2013年9月5日

UVa 338 - Long Multiplication

```#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#define PB push_back
using namespace std;

void rev(char * s) {
char * head = s, * tail = s, c;
while (*tail) {
tail++;
}
tail--;
*tail-- = c;
}
}

string removeZero(string s) {
while (s.length() > 1 && s[0] == '0') {
s = s.substr(1);
}
return s;
}

string add(string s1, string s2) {
int l1 = s1.length(), l2 = s2.length();
char result[99];
int d = 0, carry = 0;
while (l1 || l2) {
int digit = carry;
if (l1) {
digit += (s1[--l1] - '0');
}
if (l2) {
digit += (s2[--l2] - '0');
}
result[d++] = digit % 10 + '0';
carry = digit / 10;
}
if (carry) {
result[d++] = carry + '0';
}
result[d++] = 0;
rev(result);
return removeZero(string(result));
}

string simpleMut(string s, char base) {
int l = s.length();
char result[99];
int d = 0, carry = 0;
while (l) {
int digit = carry + (s[--l] - '0') * (base - '0');
result[d++] = digit % 10 + '0';
carry = digit / 10;
}
if (carry) {
result[d++] = carry + '0';
}
result[d++] = 0;
rev(result);
return removeZero(string(result));
}

void solve(string s1, string s2) {
s1 = removeZero(s1);
s2 = removeZero(s2);
int len = max(s1.length(), s2.length());
string ans = "0";
vector<string> process;
for (int pos = s2.length() - 1; pos >= 0; pos--) {
string result = simpleMut(s1, s2[pos]);
process.PB(result);
ans = add(ans, result + string(s2.length() - pos - 1, '0'));
}
len = max(len, (int)ans.length());
printf("%*s\n", len, s1.c_str());
printf("%*s\n", len, s2.c_str());
printf("%*s\n", len, string(max(s1.length(), s2.length()), '-').c_str());
int processNum = 0;
for (int i = 0; i < process.size(); i++) {
if (process[i] == "0" || (!processNum && i == process.size() - 1)) {
continue;
}
printf("%*s\n", len - i, process[i].c_str());
processNum++;
}
if (processNum > 1) {
printf("%*s\n", len, string(len, '-').c_str());
}
if (processNum != 1) {
printf("%*s\n", len, ans.c_str());
}
}

int main() {
char s[99];
while (gets(s) && s[1]) {
char s1[99], s2[99];
sscanf(s, "%s%s", s1, s2);
solve(s1, s2);
puts("");
}
return 0;
}
```