Hệ phương trình đồng dư

General
Points
65
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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}$
Draft saved