Hệ Phương Trình Đồng Dư Tổng Quát

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

Cho hệ gồm $K$ phương trình đồng dư: \[x \equiv r_i \pmod{m_i} \quad (1 \le i \le K)\] Hãy tìm số nguyên không âm $x$ nhỏ nhất thỏa mãn tất cả các phương trình trên. Nếu hệ vô nghiệm, in ra -1. Đảm bảo $\text{lcm}(m_1, m_2, \dots, m_K) \le 10^{18}$.

Dữ liệu vào
  • Dòng đầu chứa số nguyên $K$ ($1 \le K \le 100$).
  • $K$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $r_i, m_i$ ($1 \le m_i \le 10^{12}$, $0 \le r_i < m_i$).
Dữ liệu ra

Một số nguyên duy nhất là nghiệm $x$ nhỏ nhất không âm, hoặc -1 nếu vô nghiệm.

Ví dụ
Input Output
3
2 3
3 5
2 7
23
2
1 4
2 6
-1
Giới hạn
  • $1 \le K \le 100$
  • $1 \le m_i \le 10^{12}$, $\text{lcm}(m_1, \dots, m_K) \le 10^{18}$
Draft saved