모듈러 연산

큰 수를 다룰 때 오버플로를 피하기 위해 모든 중간 결과를 특정 수로 나눈 나머지로만 유지하는 연산 방식입니다.

동작 과정

예시 1: 곱셈의 분배법칙으로 오버플로 피하기
MOD = 1_000_000_007
a = 123456789, b = 987654321

직접 계산: a * b = 121932631112635269  (long 범위는 안 넘지만, 항이 누적되면 쉽게 넘친다)

안전한 방식: 매 연산마다 바로 mod를 취한다
  (a * b) % MOD
= ((a % MOD) * (b % MOD)) % MOD
= (123456789 * 987654321) % MOD
= 121932631112635269 % MOD
= 652839556

예시 2: 음수 나머지 정규화
Java의 %는 피연산자의 부호를 따른다 → (-7) % 5 = -2 (수학적 나머지 3과 다름)
정규화: ((-7 % 5) + 5) % 5 = (-2 + 5) % 5 = 3

예시 3: 나눗셈은 분배되지 않는다 → 모듈러 역원을 곱한다
MOD = 7 (소수), a = 3, b = 2  →  (a / b) % MOD 를 구하고 싶다

페르마의 소정리: MOD가 소수면  b^(MOD-2) % MOD  가 b의 모듈러 역원
  inverse(2) = 2^(7-2) % 7 = 2^5 % 7 = 32 % 7 = 4   (2 * 4 = 8 ≡ 1 mod 7 확인)

  (a / b) % MOD = (a * inverse(b)) % MOD = (3 * 4) % 7 = 12 % 7 = 5

곱셈의 분배법칙 (a * b) % m = ((a % m) * (b % m)) % m은 나머지 연산 자체의 정의에서 바로 유도됩니다. a = q1*m + r1, b = q2*m + r2로 쓰면 a*b를 m으로 나눈 나머지는 결국 r1*r2를 m으로 나눈 나머지와 같기 때문입니다. 덧셈도 같은 원리로 분배되지만, 나눗셈은 분배되지 않으므로 나누는 수의 모듈러 역원을 곱하는 방식으로 대체해야 합니다.

구현

static final long MOD = 1_000_000_007L;

// 음수가 들어와도 항상 [0, m) 범위로 정규화
static long mod(long a, long m) {
    return ((a % m) + m) % m;
}

static long addMod(long a, long b, long m) {
    return mod(a, m) + mod(b, m) >= m
            ? mod(a, m) + mod(b, m) - m
            : mod(a, m) + mod(b, m);
}

static long mulMod(long a, long b, long m) {
    return mod(a, m) * mod(b, m) % m;
}

// 거듭제곱 중간값도 매 단계 mod를 취해 오버플로를 막는다 (분할정복 거듭제곱과 동일한 분할정복 구조)
static long modPow(long base, long exp, long m) {
    if (exp == 0) {
        return 1L % m;
    }
    long half = modPow(base, exp / 2, m);
    long result = mulMod(half, half, m);
    if (exp % 2 != 0) {
        result = mulMod(result, mod(base, m), m);
    }
    return result;
}

// m이 소수일 때만 성립하는 페르마의 소정리 기반 모듈러 역원
static long modInverse(long a, long primeMod) {
    return modPow(a, primeMod - 2, primeMod);
}

복잡도

주의사항

핵심 정리

CSLOG에서 보기