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

    solution

    Đề bài: [C] Đếm số bước thuật toán Euclid tìm USCLN

    Thuật toán Euclid để tìm USCLN của a và b (a, b > 0) hoạt động như sau: lặp lại (a, b) ← (b, a mod b) cho tới khi b = 0, lúc đó a là USCLN.

    Cho a và b, hãy đếm số bước (số lần thực hiện phép thay thế) cần thiết cho tới khi b về 0.

    Ví dụ a = 48, b = 18:

    • Bước 1: (48, 18) → (18, 48 mod 18 = 12)
    • Bước 2: (18, 12) → (12, 6)
    • Bước 3: (12, 6) → (6, 0). Dừng.

    Kết quả: 3 bước.

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

      Hai số nguyên a b cách nhau khoảng trắng.

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

      1≤a,b≤10181 \le a, b \le 10^{18}1≤a,b≤1018.

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

      Một số nguyên là số bước.

    Ví dụ:

    Đầu vào:

    48 18

    Đầu ra:

    3

    Giải thích:

    Ba bước Euclid: (48,18)→(18,12)→(12,6)→(6,0).

    Đang tải editor...