Gấp Thuyền Giấy

Điểm: 3,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Assembly, C#, C++, D, Dart, Go, Groovy, Java, Javascript, Kotlin, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Ruby, Rust, Scratch, Typescript, Zig

Vasya có một tờ giấy hình chữ nhật kích thước $a \times b$ mi-li-mét với $a > b$ . Để gấp một chiếc thuyền giấy origami, Vasya luôn lấy ra một mảnh giấy hình vuông từ phần dài của tờ giấy: cắt một hình vuông $b \times b$ ra khỏi tờ giấy, gấp thành thuyền. Phần còn lại là một dải hình chữ nhật $(a - b) \times b$ .

Vasya lặp lại quá trình này với phần giấy còn lại: mỗi bước cắt một hình vuông cạnh bằng cạnh ngắn ra khỏi cạnh dài, gấp thành thuyền, rồi tiếp tục với phần còn lại. Khi đến lúc mảnh giấy còn lại đã là hình vuông, Vasya gấp nốt nó thành chiếc thuyền cuối cùng rồi dừng.

Hãy tính xem Vasya sẽ gấp được bao nhiêu chiếc thuyền.

Dữ liệu vào

Một dòng chứa hai số nguyên $a$ và $b$ ( $1 \leq b < a \leq 10^{12}$ ) — kích thước ban đầu của tờ giấy.

Dữ liệu ra

In ra một số nguyên duy nhất — tổng số thuyền mà Vasya gấp được.

Ràng buộc

$1 \leq b < a \leq 10^{12}$

Ví dụ

Input	Output	Giải thích
2 1	2	Cắt 1 hình vuông $1 \times 1$ ra khỏi tờ $2 \times 1$ , còn lại $1 \times 1$ — cắt nốt. Tổng cộng 2 thuyền.
10 7	6	Tờ $10 \times 7$ → 1 vuông $7 \times 7$ , còn $3 \times 7$ → 2 vuông $3 \times 3$ , còn $1 \times 3$ → 3 vuông $1 \times 1$ . Tổng $1 + 2 + 3 = 6$ .
1000000000000 1	1000000000000	Mỗi lần chỉ cắt được một hình vuông $1 \times 1$ , tổng cộng $10^{12}$ thuyền.

Bình luận

Không có bình luận tại thời điểm này.