Hợp Nhất Nhiều Chu Kỳ · canuc80k5409

Cho $n$ đồng dư $x \equiv b_{i} (mod a_{i})$ . Các mô-đun có thể có ước chung, và $b_{i}$ không nhất thiết nằm trong đoạn $0 \dots a_{i} - 1$ ; mỗi điều kiện chỉ phụ thuộc vào số dư của $b_{i}$ khi chia cho $a_{i}$ . Dữ liệu bảo đảm tồn tại ít nhất một nghiệm.

Hãy tìm nghiệm không âm nhỏ nhất của toàn bộ hệ điều kiện.

Input

Dòng đầu chứa $n$ . Mỗi dòng trong $n$ dòng tiếp theo chứa $a_{i}, b_{i}$ .

Output

In nghiệm không âm nhỏ nhất.

Constraints

$1 \leq n \leq 1 0^{5}$ .
$1 \leq a_{i} \leq 1 0^{12}$ ; $0 \leq b_{i} \leq 1 0^{12}$ ; $b_{i}$ được hiểu theo mô-đun $a_{i}$ .
Bội chung nhỏ nhất của các $a_{i}$ không vượt $1 0^{18}$ ; hệ luôn có nghiệm.

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 31$ và $a_{i} \leq 21$ .
Subtask $2$ ( $50%$ số điểm): không có giới hạn bổ sung.

Example

Test 1

Input

Output

Giải thích: Hai điều kiện đầu gộp thành $x \equiv 4 (mod 24)$ , nên các ứng viên đầu tiên là $4, 28, 52, \dots$ . Trong số đó, $52 mod 9 = 7$ , vì vậy $52$ là nghiệm không âm nhỏ nhất của cả ba điều kiện.

Mô hình: Ta cần tìm đại diện không âm nhỏ nhất của giao n lớp đồng dư x≡b_i (mod a_i). Các mô-đun có thể có ước chung, nhưng dữ liệu bảo đảm giao không rỗng.
Thuật toán: Giả sử các điều kiện đã xử lý tạo thành lớp x≡r (mod M). Khi thêm x≡b_i (mod a_i), đặt
Thuật toán:

text g = gcd(M,a_i), diff = b_i-r. - Thuật toán: Vì hệ có nghiệm, g chia diff. Sau khi chia cho g, ta được - Thuật toán:

text t ≡ (diff/g)·(M/g)^(-1) (mod a_i/g), - Thuật toán: rồi cập nhật - Thuật toán:

text r ← r+M·t, M ← lcm(M,a_i), - Thuật toán: và chuẩn hóa r về [0,M). Các biểu thức diff, M·t và (M/g)·a_i được tính bằng __int128 trước khi đưa về kiểu 64 bit. - Chứng minh đúng đắn: Mọi số trong lớp hiện tại có dạng r+M·t. Điều kiện mới tương đương với M·t≡b_i-r (mod a_i). Sau khi chia gcd, hệ số M/g khả nghịch modulo a_i/g, nên công thức trên cho đúng toàn bộ nghiệm của phép ghép. Lớp mới có chu kỳ lcm(M,a_i) và chứa đúng giao của các điều kiện đã xử lý. - Chứng minh đúng đắn: Quy nạp theo i cho thấy lớp cuối chứa đúng mọi nghiệm của toàn hệ. Vì r luôn được chuẩn hóa về [0,M), giá trị cuối là nghiệm không âm nhỏ nhất. - Độ phức tạp: Thời gian là O(n log A), với A=max a_i; bộ nhớ phụ là O(1) ngoài dữ liệu đã đọc. - Lỗi thường gặp: Tính (M/g)·a_i bằng kiểu 64 bit rồi mới ép sang __int128. - Lỗi thường gặp: Nhân diff/g với nghịch đảo bằng kiểu quá nhỏ. - Lỗi thường gặp: Dùng Euclid mở rộng với kiểu int, làm tràn ở các mô-đun lớn.