수학 (Mathematics)

정의

수학 (Mathematics) 은 문제 해결에 필요한 모듈러 산술 (modular arithmetic), 최대공약수/최소공배수 (GCD/LCM), 거듭제곱 (exponentiation), 합 공식 (sum formulas) 등 정수론과 대수학 기초를 포괄하는 PS 태그. solved.ac 에서 가장 많은 문제를 포함하는 범용 태그.

역사적으로 유클리드 호제법 (Euclidean Algorithm, BC 300년경), 페르마의 소정리 (Fermat’s Little Theorem, 1640), 오일러 정리 (Euler’s Theorem, 1763) 등이 현대 PS 의 모듈러 연산 / 역원 계산에 직접 쓰인다.

문제 상황과 동기

PS 에서 수학 태그는 다음 세 범주로 나뉜다.

1. 모듈러 산술: 답을 10^9 + 7 로 나눈 나머지로 요구. long long 범위 초과 방지.
2. GCD/LCM: 두 수의 공약수 / 공배수 관계. naive 반복문은 O(max(a, b)), 유클리드는 O(log min(a, b)).
3. 거듭제곱: a^N mod M 을 빠르게. naive O(N) vs 분할정복 O(log N).
4. 합 공식 / 조합: 1+2+...+N, 이항계수 C(N, K), 등. 직접 반복 vs 공식.

핵심 통찰: 나머지 연산의 distributive property 와 분할정복 이 log 복잡도를 만든다.

실무 / PS 위치: 암호학 (RSA), 해시 (rolling hash), DP 최적화, 조합론 전처리.

시각화

핵심 아이디어

모듈러 산술

(a + b) mod M = ((a mod M) + (b mod M)) mod M
(a - b) mod M = ((a mod M) - (b mod M) + M) mod M
(a · b) mod M = ((a mod M) · (b mod M)) mod M

주의: 나눗셈은 역원 필요. a / b mod M = a · b^(-1) mod M, 여기서 b^(-1) 은 b · b^(-1) ≡ 1 (mod M) 인 값. M 이 소수면 페르마의 소정리로 b^(-1) = b^(M-2) mod M.

유클리드 호제법 (GCD)

gcd(a, b) = gcd(b, a mod b)   if b ≠ 0
gcd(a, 0) = a

a mod b 가 매번 절반 이하로 줄어들어 O(log min(a, b)).

lcm(a, b) = a · b / gcd(a, b) (오버플로우 조심, a / gcd(a, b) · b 순서로).

분할정복 거듭제곱

pow(a, N, M):
    if N == 0: return 1
    half = pow(a, N/2, M)
    result = (half · half) mod M
    if N is odd: result = (result · a) mod M
    return result

O(log N). a^10 = (a^5)^2 = ((a^2 · a)^2)^2 같은 식으로.

합 공식

• 1 + 2 + ... + N = N(N+1)/2
• 1^2 + 2^2 + ... + N^2 = N(N+1)(2N+1)/6
• 등차수열 합 S = n(a + l)/2 (첫항 a, 끝항 l, 항 개수 n)

알고리즘

GCD (유클리드 호제법)

gcd(a, b):
    while b ≠ 0:
        (a, b) = (b, a mod b)
    return a

분할정복 거듭제곱

fast_pow(a, N, M):
    result = 1
    a = a mod M
    while N > 0:
        if N is odd:
            result = (result · a) mod M
        a = (a · a) mod M
        N = N / 2
    return result

모듈러 역원 (M 이 소수)

mod_inv(a, M):   # M prime
    return fast_pow(a, M - 2, M)

구현

// GCD, 거듭제곱, 모듈러 역원
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
​
ll gcd(ll a, ll b) {
  while (b) { ll tmp = a % b; a = b; b = tmp; }
  return a;
}
​
ll fast_pow(ll a, ll N, ll M) {
  ll res = 1; a %= M;
  while (N > 0) {
      if (N & 1) res = res * a % M;
      a = a * a % M;
      N >>= 1;
  }
  return res;
}
​
ll mod_inv(ll a, ll M) { return fast_pow(a, M - 2, M); }
​
int main() {
  ll a, b, N;
  cin >> a >> b >> N;
  cout << "gcd(" << a << ", " << b << ") = " << gcd(a, b) << "\n";
  cout << "lcm(" << a << ", " << b << ") = " << a / gcd(a, b) * b << "\n";
  cout << a << "^" << N << " mod " << MOD << " = " << fast_pow(a, N, MOD) << "\n";
  cout << "inverse of " << a << " mod " << MOD << " = " << mod_inv(a, MOD) << "\n";
  ll inv_a = mod_inv(a, MOD);
  cout << "verify: " << a << " * " << inv_a << " mod " << MOD << " = " << (a * inv_a % MOD) << "\n";
}

# math.gcd 내장, pow(a, N, M) 내장
import math
MOD = 10**9 + 7
​
def mod_inv(a, M):
  return pow(a, M - 2, M)
​
a, b, N = map(int, input().split())
g = math.gcd(a, b)
print(f"gcd({a}, {b}) = {g}")
print(f"lcm({a}, {b}) = {a // g * b}")
print(f"{a}^{N} mod {MOD} = {pow(a, N, MOD)}")
inv_a = mod_inv(a, MOD)
print(f"inverse of {a} mod {MOD} = {inv_a}")
print(f"verify: {a} * {inv_a} mod {MOD} = {(a * inv_a) % MOD}")

// Java BigInteger 로 GCD, pow mod
import java.math.BigInteger;
import java.util.*;
public class Main {
  static final long MOD = 1_000_000_007L;
​
  static long gcd(long a, long b) {
      while (b != 0) { long tmp = a % b; a = b; b = tmp; }
      return a;
  }
​
  static long fastPow(long a, long N, long M) {
      long res = 1; a %= M;
      while (N > 0) {
          if ((N & 1) == 1) res = res * a % M;
          a = a * a % M;
          N >>= 1;
      }
      return res;
  }
​
  static long modInv(long a, long M) { return fastPow(a, M - 2, M); }
​
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      long a = sc.nextLong(), b = sc.nextLong(), N = sc.nextLong();
      long g = gcd(a, b);
      System.out.println("gcd(" + a + ", " + b + ") = " + g);
      System.out.println("lcm(" + a + ", " + b + ") = " + (a / g * b));
      System.out.println(a + "^" + N + " mod " + MOD + " = " + fastPow(a, N, MOD));
      long inv = modInv(a, MOD);
      System.out.println("inverse of " + a + " mod " + MOD + " = " + inv);
      System.out.println("verify: " + a + " * " + inv + " mod " + MOD + " = " + (a * inv % MOD));
  }
}

12 18 1000000000

gcd(12, 18) = 6
lcm(12, 18) = 36
12^1000000000 mod 1000000007 = 469271275
inverse of 12 mod 1000000007 = 083333334
verify: 12 * 083333334 mod 1000000007 = 1

2 3 1000000006

gcd(2, 3) = 1
lcm(2, 3) = 6
2^1000000006 mod 1000000007 = 1
inverse of 2 mod 1000000007 = 500000004
verify: 2 * 500000004 mod 1000000007 = 1

복잡도

변형 / 활용

함정

1. 모듈러 뺄셈 음수

(a - b) mod M 가 음수일 수 있다. C++/Java 에서 % M 결과가 음수면 + M 필요.

ll sub_mod(ll a, ll b, ll M) {
    return ((a - b) % M + M) % M;
}

2. LCM 오버플로우

lcm(a, b) = a * b / gcd(a, b) 순서로 하면 a * b 가 long long 범위 초과 가능. a / gcd(a, b) * b 로 먼저 나누기.

3. 0의 역원 / 0으로 나누기

mod_inv(0, M) 은 정의되지 않음. 문제에서 나누는 값이 0이 아님을 보장해야.

4. M이 합성수일 때 역원

M 이 소수가 아니면 페르마 안 됨. 확장 유클리드로 gcd(a, M) == 1 확인 후 역원 계산.

5. 거듭제곱 지수가 0

pow(a, 0, M) = 1 (a=0 이어도). 0^0 은 수학적으로 논란이지만 PS 에서는 보통 1.

BOJ 연습 문제

참고

• 정수론 (소수 판정, 에라토스테네스의 체)
• 조합론 (이항계수, 카탈란 수)
• 모듈러 역원
• 중국인의 나머지 정리