사칙연산 (Arithmetic Operations)

정의

사칙연산 (Arithmetic Operations) 은 덧셈, 뺄셈, 곱셈, 나눗셈의 정확한 구현을 다루는 PS 태그. 큰 수 표현 (large integer), 오버플로우 (overflow), mod p 사칙연산, 부동소수점 정밀도 (floating point precision) 등 기본 연산의 함정을 포함.

정수 타입 범위 (int: -2^31 ~ 2^31-1, long long: -2^63 ~ 2^63-1), 부동소수점 정밀도 (double`: 15자리), mod 연산의 음수 처리 등은 모든 PS 문제에 영향.

문제 상황과 동기

PS 에서 사칙연산 태그는 다음 네 실수를 피하기 위한 검증.

1. 오버플로우: int a = 2e9; int b = 2e9; int c = a + b; → c 는 음수. long long 필요.
2. 큰 수: N 이 10^18 이상이면 long long 도 부족. Python int 또는 BigInteger, 또는 mod 연산으로 우회.
3. 나눗셈의 정수 몫: 5 / 2 = 2 (정수 나눗셈). 부동소수점 변환 조심.
4. mod 음수: C++/Java 에서 (-5) % 3 = -2 (Python 은 1). 음수 처리 필요.
5. 부동소수점 오차: 0.1 + 0.2 != 0.3 (IEEE 754). epsilon 비교.

핵심 통찰: 타입 범위를 미리 파악 하고, 중간 계산 오버플로우 를 피한다.

실무 / PS 위치: 큰 수 라이브러리, 암호학 (RSA), 정밀 수치 계산 (금융, 물리 시뮬레이션).

시각화

핵심 아이디어

정수 타입 범위

오버플로우 방지

// WRONG
int a = 2'000'000'000, b = 2'000'000'000;
int c = a + b;   // overflow, c < 0

// RIGHT
long long a = 2'000'000'000, b = 2'000'000'000;
long long c = a + b;   // OK

곱셈도 마찬가지: 10^5 × 10^5 = 10^10 > int max.

mod 연산 음수 처리

int mod(int a, int M) {
    return ((a % M) + M) % M;
}

C++/Java 에서 a % M 가 음수일 때 + M 필요. Python 은 자동 양수.

부동소수점 비교

const double EPS = 1e-9;
bool eq(double a, double b) {
    return abs(a - b) < EPS;
}

a == b 는 부동소수점에서 거의 항상 틀림. epsilon 비교.

큰 수 (Python)

a = 10**100
b = 10**100
c = a + b   # 자동으로 무제한 정밀도

Python 3 의 int 는 임의 정밀도 (arbitrary precision). 단, 시간이 길다 (곱셈 O(N log N) 또는 O(N^2)).

알고리즘

안전한 덧셈/곱셈 (C++)

safe_add(a, b, M):
    if a + b overflows:
        use long long or mod M
    return (a + b) mod M

safe_mul(a, b, M):
    return ((long long)a * b) % M

정수 나눗셈 올림

ceil_div(a, b):   # a, b > 0
    return (a + b - 1) / b

또는 (a - 1) / b + 1. 단, a=0 일 때 조심.

mod 음수 처리

mod(a, M):
    r = a % M
    if r < 0: r += M
    return r

구현

// 오버플로우 방지, mod 음수 처리
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
​
ll safe_mod(ll a, ll M) {
  return ((a % M) + M) % M;
}
​
ll safe_add(ll a, ll b, ll M) {
  return safe_mod(a + b, M);
}
​
ll safe_mul(ll a, ll b, ll M) {
  return safe_mod(a * b, M);
}
​
ll ceil_div(ll a, ll b) {   // a, b > 0
  return (a + b - 1) / b;
}
​
int main() {
  ll a, b, M;
  cin >> a >> b >> M;
  cout << a << " + " << b << " = " << a + b << "\n";
  cout << a << " * " << b << " = " << a * b << "\n";
  cout << a << " + " << b << " mod " << M << " = " << safe_add(a, b, M) << "\n";
  cout << a << " * " << b << " mod " << M << " = " << safe_mul(a, b, M) << "\n";
  cout << a << " / " << b << " (floor) = " << a / b << "\n";
  cout << a << " / " << b << " (ceil) = " << ceil_div(a, b) << "\n";
  ll neg = -17;
  cout << neg << " % " << M << " (C++) = " << neg % M << "\n";
  cout << neg << " mod " << M << " (safe) = " << safe_mod(neg, M) << "\n";
}

# 무제한 정밀도 int, mod 자동 양수
import math
​
a, b, M = map(int, input().split())
print(f"{a} + {b} = {a + b}")
print(f"{a} * {b} = {a * b}")
print(f"{a} + {b} mod {M} = {(a + b) % M}")
print(f"{a} * {b} mod {M} = {(a * b) % M}")
print(f"{a} / {b} (floor) = {a // b}")
print(f"{a} / {b} (ceil) = {math.ceil(a / b)}")
neg = -17
print(f"{neg} % {M} (Python) = {neg % M}")

// long, Math.floorMod (Java 8+)
import java.util.*;
public class Main {
  static long safeMod(long a, long M) {
      return Math.floorMod(a, M);   // 자동 양수
  }
​
  static long ceilDiv(long a, long b) {
      return (a + b - 1) / b;
  }
​
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      long a = sc.nextLong(), b = sc.nextLong(), M = sc.nextLong();
      System.out.println(a + " + " + b + " = " + (a + b));
      System.out.println(a + " * " + b + " = " + (a * b));
      System.out.println(a + " + " + b + " mod " + M + " = " + safeMod(a + b, M));
      System.out.println(a + " * " + b + " mod " + M + " = " + safeMod(a * b, M));
      System.out.println(a + " / " + b + " (floor) = " + (a / b));
      System.out.println(a + " / " + b + " (ceil) = " + ceilDiv(a, b));
      long neg = -17;
      System.out.println(neg + " % " + M + " (Java) = " + (neg % M));
      System.out.println(neg + " mod " + M + " (floorMod) = " + safeMod(neg, M));
  }
}

1000000000 2000000000 1000000007

1000000000 + 2000000000 = 3000000000
1000000000 * 2000000000 = 2000000000000000000
1000000000 + 2000000000 mod 1000000007 = 999999986
1000000000 * 2000000000 mod 1000000007 = 951432069
1000000000 / 2000000000 (floor) = 0
1000000000 / 2000000000 (ceil) = 1
-17 % 1000000007 (C++) = -17
-17 mod 1000000007 (safe) = 999999990

123456789012345678901234567890 987654321098765432109876543210 1000000007

123456789012345678901234567890 + 987654321098765432109876543210 = 1111111110111111111011111111100
123456789012345678901234567890 * 987654321098765432109876543210 = 121932631137021795226185032733622923332237463801111263526900
123456789012345678901234567890 + 987654321098765432109876543210 mod 1000000007 = 111111093
123456789012345678901234567890 * 987654321098765432109876543210 mod 1000000007 = 792363900
123456789012345678901234567890 / 987654321098765432109876543210 (floor) = 0
123456789012345678901234567890 / 987654321098765432109876543210 (ceil) = 1
-17 % 1000000007 (Python) = 999999990

복잡도

Python int 곱셈은 Karatsuba / Toom-Cook / FFT 로 O(N^1.58) ~ O(N log N). 길이 10^6 자릿수 이상은 느림.

변형 / 활용

함정

1. int 오버플로우

int a = 100000, b = 100000;
int c = a * b;   // overflow, 10^10 > 2^31

곱셈 전에 long long 으로 캐스팅: (long long)a * b.

2. 나눗셈 올림 (ceiling)

int ceil_div(int a, int b) {
    return (a + b - 1) / b;   // a, b > 0
}

(a - 1) / b + 1 은 a=0 일 때 틀림.

3. mod 음수 (C++/Java)

-17 % 5 = -2   // C++/Java
-17 % 5 = 3    // Python

C++/Java 는 ((a % M) + M) % M 또는 Java 8+ Math.floorMod(a, M).

4. 부동소수점 ==

double a = 0.1 + 0.2;
if (a == 0.3) { /* never true */ }
if (abs(a - 0.3) < 1e-9) { /* correct */ }

IEEE 754 오차로 0.1 + 0.2 = 0.30000000000000004. epsilon 비교 필수.

5. long long 도 부족한 경우

N=10^18 의 제곱은 10^36, long long (10^18) 범위 초과. Python 또는 mod 연산으로 우회.

BOJ 연습 문제

참고

• 수학 (모듈러 역원, GCD)
• 큰 수 연산
• 부동소수점 정밀도