n과 소수 p가 매우 클 때 wilson's theorem와 fermat's little theorem을 이용한 n! mod p 구하기

https://en.wikipedia.org/wiki/Wilson%27s_theorem

Wilson's theorem - Wikipedia

 

https://namu.wiki/w/%EC%9C%8C%EC%8A%A8%EC%9D%98%20%EC%A0%95%EB%A6%AC

윌슨의 정리 - 나무위키

 

1. wilson's theorem

 

2 이상의 자연수 p가 소수일 필요충분조건은 $$(p-1)! ≡ -1 (mod p)$$

 

1) 심플하지만, 몇가지 생각해봐야할 점은 p가 소수라면 (p-1)!을 p로 나눈 나머지가 -1이라는 사실을 바로 알 수 있다.

 

나머지가 -1이라는 것은 나머지가 p-1이라는 것과 동일하다.

 

2) $(p-1)! ≡ (p-1) (mod p)$가 성립하지만, 조금 더 생각해본다면...

 

p가 소수이기 때문에 p와 p-1은 서로소이고 그래서 (p-1)의 mod p에 대한 곱셈 역원이 존재한다.

 

그래서 양변에 $(p-1)^{-1} (mod p)$를 곱해준다면...

 

$$(p-2)! ≡ 1 (mod p)$$

 

 

2. 연습문제

 

17467번: N! mod P (2) (acmicpc.net)

17467번: N! mod P (2)

 

3. 풀이

 

FFT를 이용해서 빠르게 푸는 방법이 있다고 하지만 아직 이를 이해하기엔 실력이 부족

 

윌슨의 정리를 이용해서 쉽게 한번 풀어보자

 

p가 소수일때, n! mod p를 어떻게 구할 수 있을까?

 

위에서 윌슨의 정리에 의하면 $(p-2)! ≡ 1 (mod p)$까지 유도할 수 있다.

 

n > p이면, n!에는 무조건 p가 들어가기 때문에, 생각할 필요도 없이 n! mod p = 0이다.

 

하지만 문제 조건에서 n < p이므로, n = p - 1이라면, 윌슨의 정리에 의해 n! mod p = p-1이라는 것을 알 수 있다.

 

하지만 p-1보다 더 작다면?

 

$$(p-2)! = n! * (n+1)(n+2)(n+3)...(p-2) ≡ 1 (mod p)$$가 성립한다.

 

그런데 p가 소수이기 때문에 2,3,4,...,p-1과 p는 모두 서로소이다.

 

즉, (n+1)(n+2)...(p-2)는 mod p에 대한 곱셈 역원이 존재하고, 곱셈 역원의 정의에 의해...

 

$$n! ≡ ((n+1)(n+2)...(p-2))^{-1} (mod p)$$

 

그러므로, n! mod p를 구하는 대신에 (n+1)(n+2)...(p-2)의 p에 대한 곱셈의 역원을 구하는 것은 어떨까?

 

p가 소수이고, (n+1)(n+2)...(p-2)와 p가 서로소이므로 페르마의 소정리로부터..

 

$$((n+1)(n+2)...(p-2))^{p-1} ≡ 1 (mod p)$$이다.

 

$((n+1)(n+2)...(p-2))((n+1)(n+2)...(p-2))^{p-2} ≡ 1 (mod p)$이므로, (n+1)(n+2)...(p-2)의 mod p에 대한 곱셈의 역원은...

 

$$((n+1)(n+2)...(p-2))^{-1} ≡ ((n+1)(n+2)...(p-2))^{p-2} (mod p)$$

 

그러므로, $$n! ≡ ((n+1)(n+2)...(p-2))^{p-2} (mod p)$$

 

여기서 $((n+1)(n+2)...(p-2))^{p-2} (mod p)$는 분할정복을 이용한 거듭제곱을 이용해서 빠르게 구할 수 있다.

 

물론 이 과정은 n+1부터 p-2까지 곱해야하므로, n과 p의 차이가 n보다 작을때 더 빠르다고 할 수 있다.

 

n이 충분히 작다면, 굳이 p-2부터 n까지 뒤로 가는 것보다 1부터 n까지 앞으로 가는게 더 빠를테니까,

 

이 경우는 일반적으로 n! mod p를 구하는 과정처럼 1부터 n까지 곱하면서 p로 나누는 방식을 이용한다.

 

#wilson's theorem
#if p is prime, (p-1)! == p-1 mod p

def factorial(a,b):
    
    result = 1
    
    for i in range(a,b):
        
        result *= i
        result %= p
    
    return result

n,p = map(int,input().split())

if n == p-1:
    
    answer = p-1

elif n > p - n:
    
    # n! * (n+1)(n+2)(n+3)...(p-1) == p-1 mod p
    # n! * [(n+1)(n+2)(n+3)...(p-2)] == 1 mod p
    
    # because (n+1)(n+2)(n+3)...(p-2) and p is coprime,
    # (n!) mod p == ([(n+1)(n+2)(n+3)...(p-2)])^(-1) mod p
    # by fermat's little theorem, 
    # ([(n+1)(n+2)(n+3)...(p-2)])^(-1) mod p == ([(n+1)(n+2)(n+3)...(p-2)])^(p-2) mod p     
    answer = factorial(n+1,p-1)
    
    answer = pow(answer,p-2,p)

else:
    
    answer = factorial(2,n+1)

print(answer)

 

 

FFT로 구하는건 언젠가 이 실력까지 기회가 된다면...