Ghép Hai Số Dư · canuc80k5400 · Thuật toán Canuc80k

Mỗi bộ dữ liệu mô tả hai yêu cầu về số dư của cùng một số nguyên. Với bốn số a, n, b, m, cần tìm số nguyên không âm nhỏ nhất $x$ thỏa $x mod n = a$ và $x mod m = b$ . Hai mô-đun $n$ và $m$ luôn nguyên tố cùng nhau.

Ngoài $x$ , hãy in độ dài chu kỳ chung $K = n \cdot m$ ; mọi nghiệm khác có dạng $x + q K$ với $q$ nguyên.

Input

Dòng đầu chứa $T$ . Mỗi dòng trong $T$ dòng tiếp theo chứa bốn số $a$ $n$ $b$ $m$ .

Output

Với mỗi bộ dữ liệu, in $x$ $K$ trên một dòng.

Constraints

$1 \leq T \leq 1000$ .
$0 \leq a < n, 0 \leq b < m$ .
$1 \leq n, m \leq 1 0^{9}$ và $g cd (n, m) = 1$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $T \leq 5$ và $n, m \leq 29$ .
Subtask $2$ ( $50%$ số điểm): không có giới hạn bổ sung.

Example

Test 1

Input

2
2 3 3 5
1 4 3 7

Output

8 15
17 28

Giải thích: $8 mod 3 = 2$ và $8 mod 5 = 3$ , nên bộ đầu có nghiệm chuẩn $8$ và chu kỳ $3 \cdot 5 = 15$ . Ở bộ sau, $17 mod 4 = 1, 17 mod 7 = 3$ , còn chu kỳ chung bằng $4 \cdot 7 = 28$ .

Mô hình: Mỗi bộ dữ liệu cho hai điều kiện về số dư của cùng một số nguyên. Ta cần tìm nghiệm chuẩn nhỏ nhất x của hệ
Mô hình:

text x ≡ a (mod n), x ≡ b (mod m), - Mô hình: trong đó gcd(n,m)=1. Chu kỳ chung của hệ là K=n·m. - Thuật toán: Viết x=a+n·t. Thay vào điều kiện thứ hai: - Thuật toán:

text n·t ≡ b-a (mod m). - Thuật toán: Vì n và m nguyên tố cùng nhau, n có nghịch đảo modulo m. Gọi nghịch đảo đó là inv, ta có - Thuật toán:

text t ≡ (b-a)·inv (mod m). - Thuật toán: Chọn đại diện t trong [0,m-1], tính x=a+n·t, rồi chuẩn hóa x về [0,nm-1]. Mã nguồn dùng cùng một hàm ghép đồng dư tổng quát; trong bài này gcd(n,m)=1, nên công thức tự rút về định lý số dư Trung Hoa cổ điển. - Thuật toán: Các phép nhân trung gian được thực hiện bằng __int128 để tránh tràn trước khi kết quả được đưa về kiểu 64 bit. - Chứng minh đúng đắn: Nghịch đảo inv tồn tại, nên giá trị t nêu trên luôn được xác định. Khi đó x=a+n·t thỏa điều kiện thứ nhất theo cách xây dựng, đồng thời thỏa điều kiện thứ hai do phương trình đồng dư của t. - Chứng minh đúng đắn: Nếu x và y cùng thỏa hệ, thì n và m đều chia x-y. Vì hai mô-đun nguyên tố cùng nhau, nm chia x-y. Do đó chỉ có một nghiệm trong đoạn [0,nm-1], và nghiệm mà thuật toán in ra chính là nghiệm không âm nhỏ nhất. - Độ phức tạp: Mỗi bộ dữ liệu cần O(log min(n,m)) thời gian cho Euclid mở rộng và O(1) bộ nhớ phụ. - Lỗi thường gặp: Quên chuẩn hóa b-a khi giá trị này âm. - Lỗi thường gặp: Thực hiện phép nhân bằng kiểu 64 bit rồi mới ép sang __int128, khiến tràn xảy ra trước phép ép kiểu. - Lỗi thường gặp: In một nghiệm bất kỳ thay vì đại diện chuẩn 0≤x<K.