Định Lý Số Dư Trung Hoa Cơ Bản

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

Cho $T$ truy vấn, mỗi truy vấn cho bốn số nguyên $r_1, m_1, r_2, m_2$. Hãy tìm số nguyên không âm $x$ nhỏ nhất thỏa mãn hệ đồng dư: \[\begin{cases} x \equiv r_1 \pmod{m_1} \\ x \equiv r_2 \pmod{m_2} \end{cases}\] Nếu hệ vô nghiệm, 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 bốn số $r_1, m_1, r_2, m_2$ ($1 \le m_1, m_2 \le 10^9$, $0 \le r_1 < m_1$, $0 \le r_2 < m_2$).
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
2
2 3 3 5
1 4 2 6
8
-1
Giới hạn
  • $1 \le T \le 10^4$
  • $1 \le m_1, m_2 \le 10^9$
Draft saved