곱셈에 대한 역원에 관하여

* P가 소수일때 x의 곱셈에 대한 역원을 페르마의 소정리를 이용하여 구할 수 있다.

x^(P-1) = 1 (mod P) 이므로

x^(P-2) = x^(-1) (mod P) 를 얻는다.

x^(P-2)는 분할 정복을 이용하여 O(log(P))에 구할 수 있다.

* P가 소수일때 1 ~ N까지 수들의 P의 곱셈에 대한 역원(inverse)을 O(N)에 구하는 방법

cf) https://apps.topcoder.com/forums/?module=Thread&threadID=680416&start=15&mc=26 

P : modulo(ex. p = 1000000007)

inv(1) = 1

inv(x) = -(P/x) * inv(P%x) for x>1

[증명]

P % x = P - P/x*x  (mod P)

(P%x) = -P/x*x

양변을  x * (P%x) 로 나누면 아래와 같은 결과를 얻는다.

inv(x) = -P/x * inv(P%x) = ((P - P/x) * inv(P%x)) % P