목록2016/10 (1)
Code Run
곱셈에 대한 역원에 관하여
* 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) = ..
코딩 tip
2016. 10. 19. 18:16