Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Toán cho CNTT] Thuật toán Euclid mở rộng

    Thuật toán Euclid mở rộng

    Cho hai số nguyên dương a,ba, ba,b. Hãy tìm d=gcd⁡(a,b)d = \gcd(a,b)d=gcd(a,b) và cặp hệ số Bézout (x,y)(x, y)(x,y) sao cho: a⋅x+b⋅y=d.a\cdot x + b\cdot y = d.a⋅x+b⋅y=d.

    Để đảm bảo nghiệm duy nhất, hãy dùng đúng thuật toán đệ quy chính tắc dưới đây.

    Ví dụ

    a=240,b=46⇒d=2, x=−9, y=47a=240, b=46 \Rightarrow d=2,\ x=-9,\ y=47a=240,b=46⇒d=2, x=−9, y=47 vì 240⋅(−9)+46⋅47=2240\cdot(-9)+46\cdot 47 = 2240⋅(−9)+46⋅47=2.

    • Định dạng đầu vào:

      Một dòng gồm hai số nguyên dương aaa và bbb.

    • Ràng buộc đầu vào:

      1≤a,b≤1091 \le a, b \le 10^{9}1≤a,b≤109.

    • Định dạng đầu ra:

      Một dòng gồm ba số ddd, xxx, yyy theo thuật toán chính tắc.

    Ví dụ:

    Đầu vào:

    240 46

    Đầu ra:

    2 -9 47

    Giải thích:

    240*(-9)+46*47 = -2160+2162 = 2 = gcd.

    Đang tải editor...