CSES - Rectangle Cutting | Cắt hình chữ nhật

Xem PDF

Điểm: 1600 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Với một hình chữ nhật \(a \times b\), nhiệm vụ của bạn là cắt nó thành các hình vuông. Trong mỗi bước, bạn có thể chọn một hình chữ nhật và cắt nó thành hai hình chữ nhật sao cho độ dài các cạnh vẫn là số nguyên. Số bước tối thiểu là bao nhiêu?

Input

  • Gồm một dòng duy nhất chứa hai số nguyên \(a\)\(b\).

Output

  • In một số nguyên: số lần di chuyển tối thiểu.

Constraints

  • \(1 \leq a, b \leq 500\)

Example

Sample input

3 5

Sample output

3


Bình luận


  • -1
    huyhau6a2 8:26 a.m. 24 Tháng 8, 2022

    dp nhưng nó lạ lắm!