백준 7936번 N의 존재 풀이
http://boj.kr/7936 7936번: N의 존재 문제 양의 정수 m과 소수 p, 그리고 p로 나누었을 때의 나머지 a가 주어진다. 이때, nn + nm을 p로 나눈 나머지가 a가 되는 양의 정수 n이 존재하는지를 구하고, 존재하면 n..
platter.tistory.com
어제 이 문제에 대한 풀이를 썼었다. 그러면서 이산 로그를 구하는 부분은 Baby-step Giant-step 알고리즘으로 쉽게 구할 수 있다 했는데, 이번에는 이에 대해서 써보려고 한다.
4357번: 이산 로그
문제 소수 P(2 ≤ P < 231), 정수 B(2 ≤ B < P), 정수 N(2 ≤ N < P)가 주어졌을 때, 밑을 B, 나머지를 P로 하는 N의 이산 로그를 구하는 프로그램을 작성하시오. 즉, 다음과 같은 조건을 만족하는 정수 L을 찾으면 된다. BL == N (mod P) 입력 입력은 여러 개의 테스트 케이스로 이루어져 있고, 각 테스트 케이스는 한 줄로 되어져 있고, P, B, N이 공백으로 구분되어져 있다. 출력 각각의 테스트 케이스에 대해서,
www.acmicpc.net
예시 문제는 이거다.
이산 로그 문제, 소수 P, 2 이상의 정수 B,P 이하, 2 이상의 정수 N에 대해 B^L=N(modP)인 가장 작은 L을 찾아주면 된다. 페르마의 소정리에 의해 B^(P-1)=1(modP)이므로 L<P임은 자명하다.
적절한 크기의 상수 m을 잡아서 L=im+j(i,j는 m 미만의 음이 아닌 정수) 꼴로 나타낸다 하자. B^(im+j)=N(modP)형태로 나타낼 수 있다.
여기서 B^im을 우변으로 이항해주자. B^j=N*B^(-im)의 형태로 변형된다. 이때 B^(-im)은 B^im의 모듈러 인버스를 의미한다. 모듈러 인버스를 모른다면 따로 찾아보자.
그리고 우리는 i를 고정한다. 또 0부터 m-1까지의 j에 대해 B^j의 값은 미리 셋에 넣어 저장해둔다. N*B^(-im)의 값과 일치하는 B^j 값이 하나라도 존재하는지 확인하고, 존재한다면 0부터 m-1까지의 j 값에 대해 브루트포스를 하여 그 값을 찾아준다.
0부터 p/m까지의 i에 대해 이 과정을 계속 수행해준다면, 답이 존재한다면 우리는 항상 그 답을 찾을 수 있다. 아니면 답이 존재하지 않는 것이다.
이까지의 시간복잡도는 O(mlogm+(p/m)*logm)이다. mlogm은 셋에 가능한 B^j을 모두 넣는데 걸리는 시간, (p/m)logm은 모든 i에 대해 N^B(-im)과 일치하는 B^j이 존재하는지 알아보는데 걸리는 시간이다. 답이 존재할 경우 그 j를 브루트포스로 찾는데 걸리는 시간 O(m)은 O(mlogm)에 흡수되었다.
여기서 기억해야 될 점은, 우리는 m 값은 우리가 임의로 적절히 정한 상수라는 것이다. 그러면 m값을 어떻게 정해야 가장 빠른 속도를 낼 수 있을까? 시간복잡도를 인수분해하면 logm(m+p/m)이 된다. m+p/m을 m에 대해 미분하면 1-p/m^2으로, m=sqrt(p)일 때 극솟값을 가짐을 알 수 있다. 그러므로 m을 sqrt(p) 근처의 임의의 수로 정하는 것이 가장 optimal하다.
이때의 시간복잡도는 O(sqrt(p)logp)가 된다.
다음은 내가 이산 로그 문제를 푼 코드이다.
http://boj.kr/32e37f7d7d0d4143a6505bae6ab4829e
공유 소스 보기
www.acmicpc.net
개인적으로 Baby-step Giant-step 알고리즘은 알고리즘의 난이도에 비해 한국어 자료가 너무 드물어 의아했었다. 이 글이 많은 사람들에게 도움이 되었으면 좋겠다.
'PS' 카테고리의 다른 글
| 2020 3/17 problem solving (2) | 2020.03.18 |
|---|---|
| 3/16 problem solving (0) | 2020.03.17 |
| 백준 7936번 N의 존재 풀이 (0) | 2020.02.10 |
| BOJ 굿바이 2019 특별상을 받았다. (2) | 2019.12.31 |
| 나에 대하여 (1) | 2019.12.25 |
