Python `pow()` 3항 형태와 모듈러 거듭제곱 최적화

모듈러 거듭제곱이란?

기본 개념

모듈러 거듭제곱은 큰 지수 계산 결과를 특정 수로 나눈 나머지를 구하는 연산입니다.

(a^b) mod m

예를 들어, 2^10 mod 1000을 계산하려면:

일반적 방법: 2^10 = 1024 → 1024 % 1000 = 24
Python: pow(2, 10, 1000) → 24

왜 필요한가?

큰 지수를 계산할 때 문제가 발생합니다:

# ❌ 이렇게 하면 안 됩니다
result = (2 ** 1000000) % 1000000007  # 메모리 폭발!

# ✅ 올바른 방법
result = pow(2, 1000000, 1000000007)  # 빠르고 안전

`pow(a, b, m)`의 동작 원리

정의

pow(a, b, m)  # (a^b) mod m을 반환

제약 조건:

a, b, m은 모두 정수
m ≠ 0
b < 0일 때는 모듈러 역원 계산 (Python 3.8+)

시간복잡도: O(log b)

일반적인 a ** b 계산은 O(b)이지만, pow(a, b, m)은 이진 거듭제곱(Binary Exponentiation) 알고리즘을 사용하여 O(log b)에 동작합니다.

이진 거듭제곱 원리

예시: 2^10을 계산한다면

10 (이진수) = 1010₂ = 8 + 2

2^10 = 2^8 × 2^2

단계별 과정:

2^1 = 2
2^2 = 4 (제곱)
2^4 = 16 (제곱)
2^8 = 256 (제곱)
2^10 = 2^8 × 2^2 = 256 × 4 = 1024

단 4번의 곱셈으로 2^10을 계산했습니다! (일반 방법은 9번)

실제 예제

# 기본 사용
pow(2, 10, 1000)   # 24  (1024 % 1000)
pow(10, 10**14, 7) # 4

# 큰 수도 빠르게 처리
pow(2, 1000000, 1000000007)  # 0.0001초 이내

주의사항

# m = 1이면 항상 0
pow(5, 100, 1)  # 0

# b < 0인데 m이 없으면 부동소수점
pow(2, -3)      # 0.125

# b < 0이고 m이 있으면 역원 계산 (Python 3.8+)
pow(2, -1, 7)   # 4 (2의 역원)

모듈러 역원 계산

개념

모듈러 역원은 다음을 만족하는 x입니다:

(a × x) mod m = 1

즉, a로 곱했을 때 m으로 나눈 나머지가 1이 되는 수입니다.

Python 3.8+ 문법

pow(a, -1, m)  # a의 모듈러 m에 대한 역원

조건: gcd(a, m) = 1 (서로소)

예제

# 3의 역원 (mod 11)
inv = pow(3, -1, 11)  # 4
print(3 * 4 % 11)     # 1 ✓

# 7의 역원 (mod 13)
inv = pow(7, -1, 13)  # 2
print(7 * 2 % 13)     # 1 ✓

역원이 없는 경우

# gcd(6, 9) = 3 ≠ 1
pow(6, -1, 9)  # ValueError: base is not invertible

왜 역원이 필요한가?

모듈러 연산에서는 나눗셈을 직접 할 수 없습니다:

# ❌ 틀린 방법
result = (a / b) % m

# ✅ 올바른 방법
inv_b = pow(b, -1, m)
result = (a * inv_b) % m

실전 문제: 등비급수의 합

문제 상황

다음 합을 MOD = 500000009로 나눈 나머지를 구하세요:

S = 4^0 + 4^1 + 4^2 + ... + 4^(n-1)

방법 1: 반복문 (느린 방법)

n = int(input())
r = 0
MOD = 500000009
for i in range(n):
    r += pow(4, i, MOD)
    r %= MOD
print(r)

시간복잡도: O(n × log n)

n번 반복
각 반복마다 pow(4, i, MOD)는 O(log i)

문제점:

n = 10^6이면 약 수백만 번 연산
n이 커질수록 매우 느림

방법 2: 등비급수 공식 (빠른 방법)

n = int(input().strip())
MOD = 500000009
inv3 = pow(3, -1, MOD)
ans = (pow(4, n, MOD) - 1) * inv3 % MOD
print(ans)

시간복잡도: O(log n)

pow(4, n, MOD): O(log n)
pow(3, -1, MOD): O(log MOD)
나머지는 상수 시간

핵심: 등비급수 공식 사용!

등비급수 공식 유도

1단계: 기본 등비급수 공식

첫째항 a, 공비 r, 항의 개수 n인 등비급수:

S_n = a + ar + ar² + ... + ar^(n-1)

공식:

S_n = a × (r^n - 1) / (r - 1)  (단, r ≠ 1)

2단계: 유도 과정

S = a + ar + ar² + ... + ar^(n-1)     ... ①

rS = ar + ar² + ar³ + ... + ar^n      ... ②

① - ②를 계산하면:

S - rS = a - ar^n
S(1 - r) = a(1 - r^n)
S = a(1 - r^n) / (1 - r)
S = a(r^n - 1) / (r - 1)

3단계: 우리 문제에 적용

우리 문제:

첫째항 a = 1 (4^0)
공비 r = 4
항의 개수 n

S = 1 × (4^n - 1) / (4 - 1)
S = (4^n - 1) / 3

4단계: 모듈러 연산으로 변환

S mod m = (4^n - 1) / 3 mod m

문제: 모듈러 연산에서 나눗셈은 직접 불가능!

해결: 역원 사용

S mod m = (4^n - 1) × (3의 역원) mod m

5단계: 코드 구현

MOD = 500000009

# 3의 역원 계산
inv3 = pow(3, -1, MOD)

# (4^n - 1) × inv3 mod MOD
numerator = pow(4, n, MOD) - 1
ans = numerator * inv3 % MOD

주의: pow(4, n, MOD) - 1이 음수가 될 수 있으므로 최종적으로 % MOD를 한 번 더 적용하는 것이 안전합니다:

ans = (pow(4, n, MOD) - 1) * inv3 % MOD

성능 비교와 최적화

시간복잡도 비교

방법	시간복잡도	n=10^6일 때 연산 횟수
방법 1 (반복문)	O(n × log n)	~20,000,000
방법 2 (공식)	O(log n)	~20

연산 횟수 차이

방법 1:

pow(4, 0, MOD)      # 1회
pow(4, 1, MOD)      # 1회
pow(4, 2, MOD)      # 2회 (log 2)
pow(4, 3, MOD)      # 2회
...
pow(4, n-1, MOD)    # log(n-1)회

총 연산: Σ log(i) ≈ n × log(n)

방법 2:

pow(3, -1, MOD)     # log(MOD)회
pow(4, n, MOD)      # log(n)회
곱셈과 나머지 연산    # 3회

총 연산: log(MOD) + log(n) + 3 ≈ 상수

알고리즘 차이

방법 1: 매번 거듭제곱을 처음부터 계산
- 4^0, 4^1, 4^2, ... 각각 독립적으로 계산
- 이전 결과를 활용하지 못함
방법 2: 수학 공식으로 한 번에 계산
- 4^n만 계산하면 끝
- O(n) → O(log n) 혁신적 개선

최적화 팁

1. 역원 미리 계산

여러 번 나눗셈이 필요하면:

MOD = 500000009
inv3 = pow(3, -1, MOD)  # 한 번만 계산

# 여러 번 사용
result1 = (x * inv3) % MOD
result2 = (y * inv3) % MOD
result3 = (z * inv3) % MOD

2. 중간 오버플로우 방지

# ❌ 큰 수 곱셈 시 오버플로우 위험
ans = (a * b * c) % MOD

# ✅ 단계별 모듈러 연산
ans = a % MOD
ans = (ans * b) % MOD
ans = (ans * c) % MOD

3. 음수 처리

# ❌ 음수가 나올 수 있음
ans = (a - b) * inv % MOD

# ✅ 안전한 처리
ans = ((a - b) % MOD + MOD) % MOD
ans = (ans * inv) % MOD

정리

핵심 포인트

pow(a, b, m): O(log b) 시간에 모듈러 거듭제곱 계산
pow(a, -1, m): 모듈러 역원 계산 (Python 3.8+)
수학 공식 활용: 반복문을 수식으로 대체하면 극적인 성능 향상

실전 활용

알고리즘 문제: 큰 수 계산, 조합론, 확률 계산
암호학: RSA, 디지털 서명
해시 함수: 다항식 해싱

더 공부하기

페르마의 소정리 (Fermat's Little Theorem)
확장 유클리드 호제법 (Extended Euclidean Algorithm)
중국인의 나머지 정리 (Chinese Remainder Theorem)

N=가장 작은...

...양의 정수

저작자표시 비영리 변경금지 (새창열림)

붉은 각설탕

Python `pow()` 3항 형태와 모듈러 거듭제곱 최적화

모듈러 거듭제곱이란?

기본 개념

왜 필요한가?

`pow(a, b, m)`의 동작 원리

정의

시간복잡도: O(log b)

이진 거듭제곱 원리

실제 예제

주의사항

모듈러 역원 계산

개념

Python 3.8+ 문법

예제

역원이 없는 경우

왜 역원이 필요한가?

실전 문제: 등비급수의 합

문제 상황

방법 1: 반복문 (느린 방법)

방법 2: 등비급수 공식 (빠른 방법)

등비급수 공식 유도

1단계: 기본 등비급수 공식

2단계: 유도 과정

3단계: 우리 문제에 적용

4단계: 모듈러 연산으로 변환

5단계: 코드 구현

성능 비교와 최적화

시간복잡도 비교

연산 횟수 차이

알고리즘 차이

최적화 팁

1. 역원 미리 계산

2. 중간 오버플로우 방지

3. 음수 처리

정리

핵심 포인트

실전 활용

더 공부하기

티스토리툴바

Python `pow()` 3항 형태와 모듈러 거듭제곱 최적화

모듈러 거듭제곱이란?

기본 개념

왜 필요한가?

pow(a, b, m)의 동작 원리

정의

시간복잡도: O(log b)

이진 거듭제곱 원리

실제 예제

주의사항

모듈러 역원 계산

개념

Python 3.8+ 문법

예제

역원이 없는 경우

왜 역원이 필요한가?

실전 문제: 등비급수의 합

문제 상황

방법 1: 반복문 (느린 방법)

방법 2: 등비급수 공식 (빠른 방법)

등비급수 공식 유도

1단계: 기본 등비급수 공식

2단계: 유도 과정

3단계: 우리 문제에 적용

4단계: 모듈러 연산으로 변환

5단계: 코드 구현

성능 비교와 최적화

시간복잡도 비교

연산 횟수 차이

알고리즘 차이

최적화 팁

1. 역원 미리 계산

2. 중간 오버플로우 방지

3. 음수 처리

정리

핵심 포인트

실전 활용

더 공부하기

티스토리툴바

`pow(a, b, m)`의 동작 원리