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 UCLN

    Thuật toán Euclid tìm gcd⁡(a,b)\gcd(a, b)gcd(a,b) thực hiện liên tiếp (a,b)→(b,a mod b)(a, b) \to (b, a \bmod b)(a,b)→(b,amodb) cho tới khi b=0b=0b=0. Mỗi lần lặp như vậy được tính là một bước.

    Hãy đếm số bước cần thực hiện để bbb trở về 0.

    Ví dụ: a=12,b=18a=12, b=18a=12,b=18 → (12,18)→(18,12)→(12,6)→(6,0)(12,18) \to (18,12) \to (12,6) \to (6,0)(12,18)→(18,12)→(12,6)→(6,0) → 333 bước.

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

      Một dòng chứa hai số nguyên dương a b.

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

      1≤a,b≤10121 \le a, b \le 10^{12}1≤a,b≤1012.

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

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

    Ví dụ:

    Đầu vào:

    12 18

    Đầu ra:

    3

    Giải thích:

    (12,18)→(18,12)→(12,6)→(6,0): 3 bước.

    Đang tải editor...