Hệ phương trình đồng dư
Points
65
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Cho hệ gồm $N$ phương trình đồng dư: $x \equiv r_i \pmod{m_i}$ với $i = 1, 2, \dots, N$. Hãy tìm số nguyên không âm $x$ nhỏ nhất thỏa mãn cả $N$ phương trình, hoặc in ra -1 nếu hệ vô nghiệm.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên $N$ ($1 \le N \le 100$).
$N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $r_i, m_i$ ($0 \le r_i < m_i$).
Dữ liệu ra
In ra giá trị $x$ nhỏ nhất thỏa mãn, hoặc -1 nếu không tồn tại.
Ví dụ
| Input | Output |
|---|---|
| 3 2 3 3 5 2 7 |
23 |
Giới hạn
- $1 \le N \le 100$
- $1 \le m_i \le 10^9$
- $\text{lcm}(m_1, m_2, \dots, m_N) \le 10^{18}$
Community Discussion