팩토리얼(factorial)의 소수 모듈로 곱셈의 역원(modulo inverse)을 구하는 기본적인 테크닉

이미 알고있는 것들인데 블로그에 정리가 안되어 있어서

 

 

1. n!을 소수 p로 나눈 나머지

 

소수 p에 대하여 $n! mod p$를 구하는 문제가 있다.

 

단 하나의 $n! mod p$를 구해야한다면...

 

$n! = n*(n-1)*(n-2)*...*1$이므로, 1부터 n까지 $O(N)$에 다 곱한 다음, p로 나눈 나머지를 구하는 것이 간단하다.

 

하지만 n이 매우 크면서, 여러가지 n에 대한 $n! mod p$가 필요하다면 이야기가 달라진다.

 

여러가지 n에 대한 $n! mod p$가 필요하다면 가능한 모든 n에 대해 $n! mod p$를 구해놓고 O(1)로 접근하면 된다.

 

여기서 다이나믹 프로그래밍에 의해 이전에 구해놓은 값을 저장해둔다면, O(N)에 모든 n에 대해 $n! mod p$를 구할 수 있다.

 

$n! = (n-1)! * n$이므로 dp[n] = dp[n-1] * n으로 구할 수 있다.

 

n = int(input())

mod = 10**9+7 #매우 큰 소수

factorial = [0]*(n+1)
factorial[0] = 1

for i in range(1,n+1):
    
    factorial[i] = factorial[i-1]*i

print(factorial[n] % mod)

 

 

이렇게만 한다면 이론적으로 시간복잡도는 O(N)이지만 n이 매우 클 때 factorial이 매우 커져서 계산이 매우 느려진다.

 

매우 큰 수의 곱셈이 매우 느려진다는 문제가 있다.

 

그래서 보통 어떤 수 mod로 나눈 나머지를 요구하며 매번 factorial[i-1] * i를 할때마다 factorial[i]를 mod로 나눠서 저장해둔다면

 

factorial[i]값이 작아져서 계산이 매우 빨라진다.

 

이것이 가능한 이유는 모듈로 곱셈, 덧셈 연산의 성질 때문

 

https://deepdata.tistory.com/399 

정수론 - 합과 곱은 왜 계속 나눠도 문제가 없는가? -

 

 

n = int(input())

mod = 10**9+7 #매우 큰 소수

factorial = [0]*(n+1)
factorial[0] = 1

for i in range(1,n+1):
    
    factorial[i] = factorial[i-1]*i
    factorial[i] %= mod #매 곱셈마다 mod로 나눈 나머지를 저장해야 연산이 빨라짐

print(factorial[n])

 

 

2. n!의 소수 p에 대한 모듈로 곱셈의 역원

 

https://deepdata.tistory.com/577

모듈로 연산에서 나눗셈을 하는 방법(모듈로 곱셈의 역원 구하기)

 

 

이항계수 $nCr = \frac{n!}{(n-r)!r!}$을 어떤 수 p로 나눈 나머지를 구할려면 $\frac{1}{(n-r)!r!} mod p$가 필요하다.

 

$(n!)^{-1} mod p = \frac{1}{n!} mod p$를 어떻게 구할 수 있을까?

 

모듈로 연산의 성질을 잘 생각해본다면.. 아주 나이브하게 다음과 같이 구해볼 수 있을 것 같다

 

$$n! * (n!)^{-1} mod p \equiv (1*2*3*...*n) * (n^{-1} * (n-1)^{-1} * ... * 1^{-1}) mod p \equiv 1$$

 

n!은 1부터 n까지의 곱이니까, 1부터 n까지의 역원을 각각 곱해버리면 1이 될 것이다.

 

따라서 n!의 모듈로 곱셈의 역원은 정수 1부터 n까지의 역원을 곱한 것과 같다.

 

 

3. 정수 n의 소수 모듈로 곱셈에 대한 역원

 

어떤 정수 n의 소수 모듈로 곱셈에 대한 역원은 어떻게 구할 수 있을까?

 

https://deepdata.tistory.com/577

모듈로 연산에서 나눗셈을 하는 방법(모듈로 곱셈의 역원 구하기)

 

 

소수 p에 대한 모듈로 곱셈의 역원을 구하고 싶다면 페르마의 소정리를 이용하면 $O(logp)$에 구할 수 있다.

 

소수 p보다 작은 1이 아닌 정수 n은 p와 서로소이므로 페르마의 소정리에 의해 $$n^{p-1} \equiv 1 mod p$$

 

식을 변형하면 $n^{p-2} * n \equiv 1 mod p$이므로, n의 소수 p에 대한 모듈로 곱셈의 역원은 $n^{p-2}$

 

분할정복을 이용한 거듭제곱을 이용하면 $n^{p-2}$를 빠르게 구할 수 있다.

 

n**(p-2)를 하고 %p를 하면 될 것이라고 생각할 수 있지만... 위에서 설명한 (n!을 p로 나눈 나머지)와 같은 이유로

 

n이 매우 크고 p가 매우 크면 거듭제곱이 매우 커져서 나중에 p로 나눈 나머지를 구하기까지 시간이 너무 오래걸린다

 

그래서 n을 p-2번 곱할때까지 매번 곱할때마다 p로 나눈 나머지끼리 곱해야한다.

 

n mod p * n mod p * n mod p * .... n mod p 이런 식으로

 

python의 pow()함수는 pow(n, p-2, p)로 간단하게 이를 구현하게 해준다

 

따라서 (n!)^-1 mod p는 다이나믹 프로그래밍을 이용해서 다음과 같이 구할 수 있다.

 

dp = [0]*(n+1)

dp[0] = 1

 

dp[i] = dp[i-1] * pow(i,mod-2,mod)

dp[i] %= mod

 

n = int(input())

mod = 10**9+7 #매우 큰 소수

factorial = [0]*(n+1)
factorial[0] = 1

factorial_inverse = [0]*(n+1)
factorial_inverse[0] = 1

for i in range(1,n+1):
    
    #n! mod p
    factorial[i] = factorial[i-1]*i
    factorial[i] %= mod #매 곱셈마다 mod로 나눈 나머지를 저장해야 연산이 빨라짐
    
    #(n!)^-1 mod p = 1^-1 * 2^-1 ... n^-1 mod p
    # = (n-1)^-1 * n^-1 mod p
    factorial_inverse[i] = factorial_inverse[i-1] * pow(i,mod-2,mod)
    factorial_inverse[i] %= mod
    
print(factorial[n])

 

 

4. 정수 n의 모듈로 곱셈에 대한 역원

 

정수 n의 모듈로 p에 대한 곱셈의 역원을 다음과 같은 점화식으로 쉽게 구할 수 있다는 것이 알려져있다.

 

모듈로 p를 n으로 나눈 몫 p//n과 n으로 나눈 나머지 p % n(p mod n)를 이용하면 다음과 같이 나타낼 수 있다.

 

$$p = (p//n) * n + (p mod n)$$

 

양변에 mod p를 한다면 p는 p로 나눈 나머지가 0이므로.. 좌변은 0이고

 

$$0 \equiv (p//n)*n + (p mod n) mod p$$

 

양변에 $(p//n)*n mod p$를 빼준다면...

 

$$-(p//n)*n \equiv (p mod n) mod p$$

 

따라서 $$((-(p//n)n)^{-1} \equiv (p mod n)^{-1} mod p$$

 

$n^{-1}$를 구하기 위해 양변에 $(-p//n)$을 곱해준다면...

 

$$n^{-1} mod p \equiv (-p//n) * (p mod n)^{-1} mod p$$

 

여기서 핵심은 p mod n는 p를 n으로 나눈 나머지이므로 0,1,2,...,n-1중 하나이니 항상 n보다 작다.

 

그러므로 dp[n]을 n의 p에 대한 모듈로 곱셈의 역원이라고 정의하자.

 

dp[n] = -(p//n) * dp[p%n]라는 점화식으로 구할 수 있다.

 

p%n이 n보다 작으므로 dp[n]을 구하기 위해 dp[p%n]가 이전에 구해져 있다.

 

여기서 1의 p에 대한 곱셈의 역원은 1이 자명하므로 dp[1] = 1이다.

 

점화식으로 정수 n에 대한 역원을 미리 구해놓는다면, 팩토리얼의 역원은 pow(i,mod-2,mod) 대신에

 

이전에 구해놓은 정수 n에 대한 역원을 이용해서...

 

factorial_inverse[i] = factorial_inverse[i-1] * inverse[i]

 

 

n = int(input())

mod = 10**9+7 #매우 큰 소수

factorial = [0]*(n+1)
factorial[0] = 1

inverse = [0]*(n+2)
inverse[1] = 1

factorial_inverse = [0]*(n+1)
factorial_inverse[0] = 1

for i in range(1,n+1):
    
    #n^-1 mod p = -p//n * (p%n)^-1 mod p
    inverse[i+1] = -(mod//(i+1)) * inverse[mod % (i+1)]
    inverse[i+1] %= mod
    
    #n! mod p
    factorial[i] = factorial[i-1]*i
    factorial[i] %= mod #매 곱셈마다 mod로 나눈 나머지를 저장해야 연산이 빨라짐
    
    #(n!)^-1 mod p = 1^-1 * 2^-1 ... n^-1 mod p
    # = (n-1)^-1 * n^-1 mod p
    #factorial_inverse[i] = factorial_inverse[i-1] * pow(i,mod-2,mod)
    factorial_inverse[i] = factorial_inverse[i-1] * inverse[i]
    factorial_inverse[i] %= mod
    
print(factorial[n])

 

 

 

5. 페르마의 소정리를 이용한 n!의 소수 모듈로 곱셈에 대한 역원

 

https://deepdata.tistory.com/979

이항정리를 이용한 거듭제곱의 합 1^k+2^k+3^k+...+n^k 을 구하는 방법

 

 

페르마의 소정리를 이용하면 아주 간단하게 n!의 소수 p 모듈로 곱셈에 대한 역원의 점화식을 유도할 수 있다.

 

n이 소수 p보다 작다면 n! = 1*2*3*...*n에서 1부터 n은 모두 소수 p의 인수가 될 수 없으므로

 

n!과 소수 p는 서로소가 된다.

 

따라서 페르마의 소정리에 의해 $$(n!)^{p-1} \equiv 1 mod p$$

 

역시 n!을 빼낸다면... $$(n!)^{p-2} n! \equiv 1 mod p$$

 

그러므로 $$(n!)^{-1} mod p = (n!)^{p-2}$$

 

그런데 $(n!)^{p-2} n! \equiv 1 mod p$을 다시 자세히 살펴보자. n! = (n-1)! * n이므로...

 

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

 

따라서 $$(n-1)!^{-1} mod p = (n!)^{p-2} * n = (n!)^{-1} * n$$

 

dp[n]을 n!의 소수 p 모듈로 곱셈에 대한 역원이라고 정의하자.

 

먼저 $dp[n] = (n!)^{-1} mod p = (n!)^{p-2}$를 분할정복을 이용한 거듭제곱으로 구해놓는다.

 

여기서 n! mod p는 이미 앞에서 구해놓았다.

 

dp[n-1] = dp[n] * n으로 n부터 시작해서 거꾸로 n,n-1,n-2,...,1까지 순회하면

 

n! 소수 p 모듈로 곱셈에 대한 역원을 다이나믹 프로그래밍으로 간단하게 구할 수 있다

 

 

n = int(input())

mod = 10**9+7 #매우 큰 소수

factorial = [0]*(n+1)
factorial[0] = 1

for i in range(1,n+1):
    
    #n! mod p
    factorial[i] = factorial[i-1]*i
    factorial[i] %= mod #매 곱셈마다 mod로 나눈 나머지를 저장해야 연산이 빨라짐

factorial_inverse = [0]*(n+1)
factorial_inverse[n] = pow(factorial[n], mod-2, mod)

#(n-1)!^-1 mod p = n!^-1 mod p * n
for i in range(n,0,-1):

    factorial_inverse[i-1] = factorial_inverse[i] * i
    factorial_inverse[i-1] %= mod
    
print(factorial[n])

 

 

 

 

https://rebro.kr/107

PS를 위한 정수론 - (4) 이항 계수 (nCr mod P) 구하는 다양한 방법

 

https://koosaga.com/63

이항계수 (nCr) mod p 계산하기