Cho hai số nguyên dương a và b. Hãy tìm hệ số Bézout x,y của gcd(a,b) và chọn cặp tối ưu theo quy tắc của đề. Gọi g=gcd(a,b). Trước hết tối thiểu hóa ∣x∣+∣y∣; nếu hòa, ưu tiên cặp có x≤y, rồi chọn x nhỏ hơn.
Input
Một dòng chứa a và b.
Output
In xy theo thứ tự tối ưu đã nêu.
Constraints
1≤a,b≤109.
Scoring
Subtask 1 (50% số điểm): các test từ 1 đến 10, dùng miền dữ liệu nhỏ để có thể đối chiếu độc lập.
Subtask 2 (50% số điểm): không có giới hạn bổ sung ngoài các ràng buộc đã nêu.
Example
Test 1
Input
35 15
Output
1 -2
Giải thích: Ta có 35⋅1+15⋅(−2)=5=gcd(35,15); trong họ nghiệm, cặp này đạt tổng trị tuyệt đối nhỏ nhất theo quy tắc phân xử.
Lời giải tóm tắt
Ý tưởng: Gọi g=gcd(a,b). Thuật toán Euclid mở rộng cho một nghiệm (x0,y0) của a·x+b·y=g. Mọi nghiệm có dạng
Ý tưởng:x=x0+(b/g)·t, y=y0-(a/g)·t, với t nguyên.
Ý tưởng: Hàm mục tiêu |x|+|y| chỉ có thể đổi chiều tại các vị trí mà x hoặc y đổi dấu. Vì vậy chỉ cần xét các giá trị nguyên của t ở quanh -x0/(b/g) và y0/(a/g), cùng vài lân cận để tránh sai số chia nguyên. So sánh các ứng viên theo thứ tự: tổng trị tuyệt đối nhỏ hơn; nếu hòa, ưu tiên điều kiện x≤y; nếu vẫn hòa, chọn x nhỏ hơn.
Ý tưởng: Dùng __int128 khi tính nghiệm và hàm mục tiêu. Độ phức tạp là O(log min(a,b)).