Căn Bậc K Modulo Nguyên Tố

Buổi 58 — Modular Arithmetic
Points
98
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
number
Submissions
Đề bài

Cho số nguyên tố $P$ và hai số nguyên $K, A$ ($1 \le K \le 10^9$, $0 \le A < P \le 10^9 + 7$). Hãy tìm số nguyên $x \in [0, P-1]$ nhỏ nhất thỏa mãn: \[x^K \equiv A \pmod P\] Nếu không tồn tại $x$ thỏa mãn, in ra -1.

Dữ liệu vào
  • Dòng đầu chứa số nguyên $T$ ($1 \le T \le 20$).
  • $T$ dòng tiếp theo, mỗi dòng chứa ba số $P, K, A$.
Dữ liệu ra

Với mỗi truy vấn, in ra nghiệm $x$ nhỏ nhất hoặc -1.

Ví dụ
Input Output
3
11 3 8
11 2 2
1000000007 2 4
2
-1
2
Giới hạn
  • $1 \le T \le 20$
  • $2 \le P \le 10^9 + 7$ ($P$ nguyên tố)
  • $1 \le K \le 10^9$, $0 \le A < P$
Draft saved