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--;
  while (head < tail) {
    c = *head;
    *head++ = *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;
}

沒有留言:

張貼留言