Phương Trình Đồng Dư Tuyến Tính

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

Cho ba số nguyên $A, B, M$ ($1 \le M \le 10^9$, $0 \le A, B < M$). Hãy tìm số nguyên không âm $x$ nhỏ nhất thỏa mãn: \[A \cdot x \equiv B \pmod M\] Nếu không tồn tại nghiệm $x$, hãy in ra -1.

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

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

Ví dụ
Input Output
3
4 2 6
4 3 6
0 0 5
2
-1
0
Giới hạn
  • $1 \le T \le 10^4$
  • $1 \le M \le 10^9$, $0 \le A, B < M$
Draft saved