Hệ Phương Trình Đồng Dư Tổng Quát
Points
42
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Đề 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}$
Community Discussion