Căn Bậc K Modulo Nguyên Tố
Points
98
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
number
Đề 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$
Community Discussion