이산 로그

문제

소수 $p$와 정수 $a$, $b$가 주어진다. $a^x \equiv b \pmod{p}$를 만족하는 최소 양의 정수 $x$를 구하라. 조건을 만족하는 $x$가 존재하지 않으면 $-1$을 출력하라.

이산 로그 문제는 거듭제곱의 결과값이 주어졌을 때 지수를 역으로 찾는 문제이다. 소수 모듈러 연산에서 이 값을 효율적으로 구하기 위해 $O(\sqrt{p})$의 시간 복잡도를 가지는 Baby-step Giant-step 알고리즘을 쓰도록 한다.

입력

첫째 줄에 소수 $p$, 정수 $a$, $b$가 공백으로 구분되어 주어진다.

• $2 \le p \le 10^9$ ($p$는 소수)
• $1 \le a < p$
• $1 \le b < p$

출력

$a^x \equiv b \pmod{p}$를 만족하는 최소 양의 정수 $x$를 한 줄에 출력한다. 단, $x = 0$은 정답에서 제외되며 1 이상의 값만 고려한다. 해가 존재하지 않으면 $-1$을 출력한다.

예제 입력 1

5 2 3

예제 출력 1

3

예제 입력 2

7 3 4

예제 출력 2

4