이산 로그를 찾아라
다이아몬드 IV의견: 0
소수 \(p\)와 정수 \(a\), \(b\)가 주어진다. \(a^x \equiv b \pmod{p}\)를 만족하는 정수 \(x\)가 존재하는지 판별하고, 존재한다면 \(0 \le x < p\) 범위에서 그러한 \(x\)를 하나 출력하여라. 존재하지 않으면 \(-1\)을 출력한다.
여러 개의 질의가 주어진다. \(p\)가 크므로 \(0\)부터 차례로 시도하는 풀이는 통과할 수 없다.
\(1 \le Q \le 100\)
\(2 \le p \le 10^9\), \(p\)는 소수
\(0 \le a, b < p\)
첫 줄에 질의의 수 \(Q\)가 주어진다.
다음 \(Q\)개의 줄에 각각 세 정수 \(p\), \(a\), \(b\)가 주어진다. \(p\)는 소수이다.
각 질의에 대해 \(a^x \equiv b \pmod{p}\)를 만족하는 \(x\) (\(0 \le x < p\)) 하나를, 없으면 \(-1\)을 한 줄에 출력한다.
2
13 2 8
13 2 5
3
9\(2^x \equiv 8 \pmod{13}\): \(2^3 = 8\)이므로 \(x = 3\) (다른 해도 인정). \(2^x \equiv 5 \pmod{13}\): 2의 거듭제곱은 13을 법으로 1,2,4,8,3,6,12,...이며 5가 나오므로 해가 존재한다.
2
7 2 0
5 1 2
-1
-1\(2^x \equiv 0 \pmod 7\)은 불가능하므로 \(-1\). \(1^x \equiv 2 \pmod 5\)도 \(1^x\)은 항상 1이라 불가능하므로 \(-1\).
riseoj 작성
출처 Original
평가 및 의견
이산 로그를 찾아라
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
이산 로그를 찾아라