큰 수의 연산들

큰수의 연산

long long 범위를 넘어가는 수에 대해서 가끔 연산을 수행해야하는 경우가 있다. 이 경우 string을 통해 연산해야한다. 프로그래밍 대회나 문제풀이에서 가끔 보이니 익혀두는게 좋을 것 같아서 따로 정리해보려고 한다.

이 포스트에서는 반복적으로 수가 더해지거나 곱해져서 input이 커진 경우가 아닌 (이 경우는 다른 포스트에서 다룰 예정), 처음부터 long long 범위를 벗어나는 input에 대한 처리를 다룬다.

 

 

1. 덧셈

string addition (string a, string b) {
  string result;

  int flag_a = 0, flag_b = 0;

  if (a[0] == '-') flag_a = 1;
  if (b[0] == '-') flag_b = 1;


  if (flag_a && !flag_b) return substraction(b, a.substr(1));
  if (!flag_a && flag_b) return substraction(a, b.substr(1));

  if (flag_a && flag_b) {
      a = a.substr(1);
      b = b.substr(1);
  }
  
  int len_a = a.length();
  int len_b = b.length();

  for (int i = 0; i < abs(len_a-len_b); i++) {
        if (len_a > len_b) b = '0' + b;
        else a = '0' + a;
  }


  int length = a.length();
  int carry = 0, sum = 0;

  for (int i = length-1; i >= 0; i--) {
      sum = carry + a[i]-'0' + b[i]-'0';
  
      if (sum >= 10) carry = 1, sum -= 10;
      else carry = 0;

      result =  char(sum + '0') + result;
  }

    if (carry > 0) result = char(carry +'0') + result;

    while (result.length() > 1 && result[0] == '0') {
        result = result.substr(1);
    }
  
  if (flag_a && flag_b) result = '-' + result;

  return result;
}

 

 

 

2. 뺄셈

string substraction (string a, string b) {
    string result;

    int flag_a = 0, flag_b = 0;


  if (a[0] == '-') flag_a = 1;
  if (b[0] == '-') flag_b = 1;

  
  if (flag_a && !flag_b) return addition(a, '-' + b);
  if (!flag_a && flag_b) return addition(a, b.substr(1));

    if (flag_a && flag_b) {
      a = a.substr(1);
      b = b.substr(1);
  }


    int len_a = a.length();
    int len_b = b.length();

    for (int i = 0; i < abs(len_a-len_b); i++) {
        if (len_a > len_b) b = '0' + b;
            else a = '0' + a;
    }

    int k = 0, flag = 0;
    while (k != a.length()) {        
        if (a[k]-'0' < b[k]-'0') {
            swap(a, b);
            swap(len_a, len_b);
            flag = 1;
        }

        else if (a[k]-'0' > b[k]-'0') break;
        else k++;
    }


    int length = a.length();
    int borrow = 0, sub = 0;

    for (int i = length-1; i >= 0; i--) {
        sub = ((int)(a[i]-'0') - borrow) - (int)(b[i]-'0');
    
        if (sub < 0) borrow = 1, sub += 10;
        else borrow = 0;

        result = char(sub + '0') + result;

    }

    while (result.length() > 1 && result[0] == '0') {
        result = result.substr(1);
    }

    if (!(flag_a && flag_b) && (flag)) result =  "-" + result;
    if ((flag_a && flag_b) && !(flag)) result =  "-" + result;

    return result;
}

 

 

3. 곱셈

고속 푸리에 변환을 알아야한다.

string multiplication (string a, string b) {
  string result;
  
  
  
  
  
  return result;
}

 

 

4. 나눗셈

string division (string a, string b) {
  string result;
  
  
  
  
  
  return result;
}

 

 

 

5. 거듭제곱

string power (string a, string b) {
    int n = stoi(a);
    int r = stoi(b);
    
    string result = to_string(pow(n, r)); // #include <cmath>
    result = result.substr(0, result.find("."));
  
    return result;
}

 

 

 

6. 모듈러 연산

int modulo (string a, string b) {
    int remainder = 0;
  	int k = stoi(b);
    int length = a.length();

    for (int i = 0; i < length; i++) {
        remainder = (remainder * 10 + (a[i]-'0'))%k;
    }
  
  return remainder;
}

 

 

 

종합코드

#include <iostream>
#include <string>

using namespace std;

string addition (string, string);
string substraction (string, string);
string multiplication (string, string);
string division (string, string);
string modulo (string, string);
string power (string, string);


int main() {
    string s1, s2;
    cin >> s1 >> s2;

    cout << addition(s1, s2) << endl;
    cout << substraction(s1, s2) << endl;
    cout << modulo(s1, s2) << endl;
    cout << power(s1, s2) << endl;

    return 0;
}