PS 1271

ps1271.cc

// Solution for https://www.acmicpc.net/problem/1271

#include <algorithm>
#include <iostream>
#include <string>
#include <stdexcept>
#include <utility>

#include <sstream>

void assert_positive_integer(const std::string& x) {
  for (char e : x) {
    if (e < '0' || e > '9') {
      throw std::runtime_error(std::string("Not a positive integer: ") + x);
    }
  }
}

// Remove leading zeros from BigInteger x
std::string remove_leading_zeros(const std::string& x) {
  int n_leading_zero = 0;
  while (n_leading_zero < x.length()) {
    if (x[n_leading_zero] != '0') {
      break;
    }
    ++n_leading_zero;
  }
  std::string result = x.substr(n_leading_zero);
  if (result.empty()) {
    result = "0";
  }
  return result;
}

// Compare BigInteger x and BigInteger y
// Return -1 if x < y; 0 if x == y; 1 if x > y
int compare(const std::string& x, const std::string& y) {
  if (x.length() > y.length()) {
    return 1;
  } else if (x.length() < y.length()) {
    return -1;
  }

  // if x and y are same length
  // compare lexicographically
  if (x == y) {
    return 0;
  }
  if (std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end())) {
    return -1;
  } else {
    return 1;
  }
}

// Compute x + y, where x and y are BigInteger
std::string add(const std::string& x, const std::string& y) {
  std::string result;

  // Reverse string so that the 1's digit is at index 0
  std::string x_copy{x}, y_copy{y};
  if (x.length() < y.length()) {  // assume: length(x) >= length(y)
    std::swap(x_copy, y_copy);
  }
  std::reverse(x_copy.begin(), x_copy.end());
  std::reverse(y_copy.begin(), y_copy.end());

  int carry_over = 0;

  for (int i = 0; i < x_copy.length(); ++i) {
    int x_digit = x_copy[i] - '0';
    int y_digit = (i < y_copy.length() ? y_copy[i] - '0' : 0);
    int s = x_digit + y_digit + carry_over;
    if (s >= 10) {
      carry_over = 1;
      s -= 10;
    } else {
      carry_over = 0;
    }
    result.push_back(s + '0');
  }
  if (carry_over != 0) {
    result.push_back(carry_over + '0');
  }
  std::reverse(result.begin(), result.end());
  return remove_leading_zeros(result);
}

// Compute x - y, where x and y are BigInteger
// Assume: x >= y
std::string subtract(const std::string& x, const std::string& y) {
  if (compare(x, y) < 0) {
    throw std::runtime_error("x must be greater than or equal to y");
  }
  int borrowed = 0;
  std::string result;

  // Reverse string so that the 1's digit is at index 0
  std::string x_copy{x}, y_copy{y};
  std::reverse(x_copy.begin(), x_copy.end());
  std::reverse(y_copy.begin(), y_copy.end());

  for (int i = 0; i < x_copy.length(); ++i) {
    int x_digit = x_copy[i] - '0';
    int y_digit = (i < y_copy.length() ? y_copy[i] - '0' : 0);
    int s = x_digit - y_digit - borrowed;
    if (s < 0) {  // need to borrow from next digit
      borrowed = 1;
      s += 10;
    } else {
      borrowed = 0;
    }
    result.push_back(s + '0');
  }
  std::reverse(result.begin(), result.end());
  return remove_leading_zeros(result);
}

// Multiply BigInteger x by y, where 1 <= y <= 9
std::string multiply_by_single_digit(const std::string& x, int y) {
  if (y < 1 || y > 9) {
    throw std::runtime_error("y must be between 1 and 9");
  }

  std::string product;
  // Reverse string so that the 1's digit is at index 0
  std::string x_copy{x};
  std::reverse(x_copy.begin(), x_copy.end());
  int carry_over = 0;
  for (char digit : x_copy) {
    int digit_prod = (digit - '0') * y + carry_over;
    product.push_back((digit_prod % 10) + '0');
    carry_over = digit_prod / 10;
  }
  if (carry_over != 0) {
    product.push_back(carry_over + '0');
  }
  // Reverse before returning
  std::reverse(product.begin(), product.end());
  return product;
}

// Divide BigInteger x by BigInteger y
// Returns (quotient, remainder)
std::pair<std::string, std::string>
divide(const std::string& x, const std::string& y) {
  /* Special cases */
  if (compare(x, y) < 0) {  // x < y
    return {"0", x};
  }
  if (x.length() == y.length()) {
    // x, y have same number of digits; quotient is a single digit
    int k;
    std::string p;
    for (k = 9; k >= 1; --k) {
      p = multiply_by_single_digit(y, k);
      if (compare(p, x) <= 0) {
        break;
      }
    }
    return {std::to_string(k), subtract(x, p)};
  }

  // Take first D digits of x, where D = number of digits in y
  // Save this number to the variable dividend
  int d = y.length();
  std::string dividend = x.substr(0, d);
  // If the first D digits are less than y, add 1 more digit
  if (compare(dividend, y) < 0) {
    dividend.push_back(x[d]);
    ++d;
  }
  
  // Now we will compute dividend / y. The quotient will be between 1 and 9.
  int k;
  std::string p;
  for (k = 9; k >= 1; --k) {
    p = multiply_by_single_digit(y, k);
    if (compare(p, dividend) <= 0) {
      break;
    }
  }
  std::string quotient = std::to_string(k) + std::string(x.length() - d, '0');
  std::string remainder;
  auto dividend_next = subtract(x, p + std::string(x.length() - d, '0'));

  if (compare(dividend_next, y) >= 0) {
    auto [quotient_next, remainder_next] = divide(dividend_next, y);
    quotient = add(quotient, quotient_next);
    remainder = remainder_next;
  } else {
    // Next dividend is already smaller than y
    remainder = dividend_next;
  }

  return {quotient, remainder};
}

int main() {
  std::string n, m;

  std::cin >> n >> m;

  assert_positive_integer(n);
  assert_positive_integer(m);
  
  if (compare(m, n) > 0) {
    std::cout << 0 << "\n" << n << std::endl;
    return 0;
  }

  auto [q, r] = divide(n, m);
  std::cout << q << "\n" << r << std::endl;

  return 0;
}