VM 08 Bài 05 - Số nguyên

Xem dạng PDF
Gửi bài giải
Điểm: 0,26 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Nguồn bài:
VNOI Marathon '08 - Round 4Problem Setter: Nguyễn Minh Hiếu
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Tìm hai số nguyên không âm ~x_1~ và ~x_2~ thỏa mãn ~a_1 \times x_1 + b_1 = a_2 \times x_2 + b_2~ và ~x_1 + x_2~ là nhỏ nhất. Biết rằng luôn tồn tại số ~x_1, x_2~ thỏa mãn.

Input

Gồm 1 dòng 4 số nguyên ~a_1, b_1, a_2, b_2~ (các số nguyên không âm trong phạm vi ~[0, 2^{31} - 1]~).

Output

Ghi ra 2 số ~x_1, x_2~ thỏa mãn yêu cầu đề bài.

Sample Input

3 4 5 5

Sample Output

2 1

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 0
    Thien2009  đã bình luận lúc 20, Tháng 4, 2026, 14:57 ← sửa 3

    một vài lưu ý có thể xem là spoil

    hàm __gcd(a,b) của cpp có thể trả về giá trị âm

    sau khi có nghiệm của phương trình ax + by = c a => 0 && b <= 0 x,y có thể âm

    ax + ab/gcd(a,b) - ab/gcd(a,b) + by = c; => a(x - b/gcd(a,b)) + b(y - a/gcd(a,b)) = c /// phép biến đổi để tăng x,y => a(x + b/gcd(a,b)) + b(y + a/gcd(a,b)) = c /// phép biến đổi để giảm x,y

    nếu a = 0 => x = 0, nếu b = 0 => y = 0

    cẩn thận phép chia 0