모듈러 역공학

경쟁 프로그래밍 문제 중에는 출력이 유리수 $\frac{p}{q}$인 경우, 그 대신 $pq^{-1} \bmod m$을 출력하라고 요구하는 문제가 있다. 여기서 $m$은 소수이다. 그런데 프로그램이 틀린 답을 낼 때 이 값을 디버깅하기는 어렵다. $q^{-1}$을 손으로 계산하기도 힘들고, 작은 유리수에 대해서도 이 값의 크기가 아주 커질 수 있기 때문이다. 예를 들어 $1 \cdot 2^{-1} \bmod 97 = 49$이다.

풀이를 빠르게 디버깅하려면 $pq^{-1} \bmod m$이 주어졌을 때 $p$와 $q$를 복원하는 프로그램을 만들고 싶다. 가능한 $p$와 $q$의 값은 유일하지 않지만, 범위를 좁히는 데 도움이 되는 정보가 있다. 바로 $\frac{p}{q}$를 보통의 유리수로 해석했을 때 어떤 정수 $x$에 대해 $[x, x + 1)$ 범위에 있다는 것이다.

세 값 $v$, $x$, $m$이 주어질 때, $0 \leq p, q < m$이고 $pq^{-1} \equiv v \bmod m$이며 $x \leq \frac{p}{q} < x + 1$을 만족하는 $p$의 최솟값과 그에 대응하는 $q$를 구하라.

입력은 한 줄이며, 공백으로 구분된 세 정수 $v$, $x$, $m$이 주어진다. 여기서 $3 \leq m \leq 10^6$, $1 \leq v < m$, $0 \leq x < m$이고 $m$은 소수이다.

$0 \leq p,q < m$, $pq^{-1} \equiv v \bmod m$, $x \leq \frac{p}{q} < x + 1$을 만족하는 최소 정수 $p$와 그에 대응하는 $q$를 출력한다. 그러한 $p$와 $q$가 여러 쌍이면 $p$가 최소인 쌍을 출력한다. 그러한 $p$와 $q$가 존재하지 않으면 대신 $-1$ 하나를 출력한다.