String Hashing - Algorithms for Competitive Programming (cp-algorithms.com) String Hashing - Algorithms for Competitive Programming String Hashing Hashing algorithms are helpful in solving a lot of problems. We want to solve the problem of comparing strings efficiently. The brute force way of doing so is just to compare the letters of both strings, which has a time complexity of $O(\mi cp-algori..
1. 오일러의 정리(Euler's theorem) a와 n이 서로소인 양의 정수이면, 다음이 성립한다 $$a^{\varphi(n)} \equiv 1 (mod n)$$ 여기서 $\varphi(n)$은 n에 대한 오일러 phi 함수이다. 서로소가 아니라면 다음과 같이 쓸 수 있다. $$a^{\varphi(n) + 1} \equiv a (mod n)$$ n이 소수 p이면, $\varphi(p) = p-1$이므로, a,p가 서로소이면 $a^{p-1} \equiv 1 (mod p)$이다. 페르마의 소정리는 오일러의 정리의 특수한 케이스이다. 2. 거듭제곱을 어떤 정수로 나눈 나머지 $a^{n}$을 어떤 정수 p로 나눈 나머지는 어떻게 구할 수 있을까? $a^{n}$을 직접 계산한 다음에, p로 나눈 나머지를 구하..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
