TodayILearned : Day 7 모듈러 역원 Modulo Inverse

1. 지수승 빠르게 연산하기 exponential squaring

n의 10000제곱을 구할 때 단순히 10000번 곱하는 방법은 시간복잡도 O(n), 꽤나 느린 편이다. 이를 극복하기 위해서 2^128 = 4^64 = 4 ^ 32 = 16 ^ 16 … = 2^128 * 1 128번 걸리던 연산을 계속해서 두 번 곱해주는 꼴로 바꿔주면 logn번만에 연산이 끝난다.

# multiply 
O(n)
n = 100000 
ans = 1
for _ in range(n):
    ans *= 2

# vs squaring 
# O(logn)
n = 100000 
ans = 2 ** n

def fast_exponent(x, n) 
	left_term = 1
	while(n > 1):
		if n % 2 == 0:
			x = x ** 2
			n = n // 2
		else: 
			x = x ** 2
			n = (n - 1) // 2
			# x^7 = x * ((x ^ 2)^3)
			# 나머지는 left_term에 곱해준다. 
			left_term *= x
	result = x * left_term
	return result

y = x ** 10

그렇지만 파이썬 사용자가 체감하지 못하는 이유는 무엇일까, 이미 파이썬의 ** 연산자가 O(logn)을 갖도록 설계되어 있기 때문일 거다.

2. modulo inverse

왜 필요한데? 문제의식

(3 x 10^201 x 70경 / 9000경 * 9000해 ) mod 1000000007 = 는 어떻게 구할수 있을까? 이 값을 실제로 계산해서 풀려고 하면 아무리 컴퓨터라고 하더라도 시간이 너무 많이걸린다. 그래서 mod를 계산이 다 끝나고 적용하지 않고 계산 중간에 적용할 수 있는 방법을 찾고싶다. 간단해 보이는 문제지만 배우지 않으면 절대 풀 수 없다.

페르마의 정리

$a^p \equiv a$ (mod p)

$a^p$ 와 a 모두 p으로 나눈 나머지가 같다.
단 p은 소수이며 a는 p의 배수가 아니다. (a가 p의 배수면 당연히 mod p 값은 0이 나오기 때문에 식은 성립하지만 의미가 없다.)
예제 ) $5^{3 } \equiv 5$ (mod 3). 125를 3으로 나누면 나머지 2, 5를 3으로 나누면 나머지 2

모듈러의 역원?

$a^{p - 1} \equiv 1$ (mod p)

$a^{p - 2} \equiv$ a^-1 (mod p)

집중하지 않으면 내용이 잘 이해가 안갈 수 있다.

가장 중요한 것, a ^-1, 처음 이 문자를 보았을 때 $a^{-1}$ or $\left( \frac{1}{a} \right)$ 처럼 생겨서 분수라고 생각할 수 있지만 결코 아니다. 오히려 보통의 경우 상당히 큰 자연수이다.

이 a ^-1을 modulo inverse라고 정의하고 ** $a^{p-2}$ **으로 직접 구할 수 있다. 다만 재밌는 것은 a ^-1를 mod가 있는 식에서 사용할 때는 $\left( \frac{1}{a} \right)$ 처럼 사용할 수 있다는 것이다. 잔말말고 예제로 알아보자.

n = $2^{2048}$ , r = $7^{215}$ , p = 1000000007 일 때 $(n/r)$ mod p ?
p값은 아주 큰 소수이며, n과 r은 상상하기도 힘든만큼 큰 수이다. 이 때 어려운 나누기를 하고 mod를 계산하는 대신 $(n/r)$ mod p = $n\times\left( \frac{1}{r} \right)$ mod p 로 바꿀 수 있다.
$\left( \frac{1}{r} \right)$ 은 r ^-1으로 바꿀 수 있다고 했고 이는 $r^{p-2}$ 라고 했다. 따라서 식은
$(n \times r^{p-2})$ mod p = $((n \times$ mod p $)$ $\times(r^{p-2}$ mod p $)$ mod p $)$ 가 된다. 이게 얼마나 큰 차이인지 알겠는가? mod p를 각각의 수에 적용할 수 있다는 건 시간 복잡도에서 큰 차이를 줄여준다.
moduler inverse는 mod p를 시행하는 큰 수들 간의 나눗셈을 곱셈으로 바꿔줄 수 있다는 것이 중요하다.

nCr 계산법

나누기를 곱셈으로 바꿀 수 있다.

$(n!) / (n-r)!r!$ mod p $\equiv$ $(n!) * ((n-r)!r!)^{p-2}$ mod p

3. 코드 및 중요 팁

$(n-1!)^{-1} == n * (n!)^{-1}$ 이기 때문에 n!의 인버스만 알면 인버스 배열 역시 O(n)에 채울 수 있다. 고로 O(n + logp)

memo = [-1] * 2000002
memo[0] = 1
memo_inverse = [-1] * 2000002
memo_inverse[0] = 1
exp_list = [1] * 100001 

def build_exp2(m, mod):
    for i in range(1, m + 1):
        exp_list[i] = (2 * exp_list[i - 1]) % mod
# O(n)
def build_factorial(n, mod):
    for i in range(1, n + 1):
        memo[i] = (memo[i - 1] * i) % mod
    return 

# O(n + logp) 중요 
def build_fast_inverse(n, mod):
    n_fact = memo[n]
    n_fact_inv = exponention_fast(n_fact, mod - 2, mod)
    memo_inverse[n] = n_fact_inv
    k_fact_inv = n_fact_inv
    for k in list(range(2, n + 1))[::-1]:
        k_minus1_fact_inv = (k_fact_inv * k) % mod
        memo_inverse[k - 1] = k_minus1_fact_inv
        k_fact_inv = k_minus1_fact_inv
    return 

def exponention_fast(x, n, mod):
    y = 1
    while(n > 1):
        x = x % mod
        if n % 2 == 0:
            x = x ** 2
            n = n // 2
        else:
            y *= x
            x = x ** 2
            n = (n - 1) // 2
    return x * y

def comb(n, p, mod):
    if n <= p:
        return 1
    a = memo[n]
    b = memo_inverse[p]
    c = memo_inverse[n - p]
    
    return (((a * b) % mod) * c) % mod