Cắt hình vuông ít nhất


Submit solution

Points: 3
Time limit: 1.0s
Memory limit: 977M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Hôm nay Tichpx hẹn hò với Crush đi xem phim nhưng khi đến cổng nhà nàng chờ nàng trang điểm lâu quá. Tichpx nhặt được một miếng bìa hình chữ nhật cạnh nguyên, may mắn thay hôm nay mang theo kéo Tichpx cắt hình chữ nhật thành 2 hình chữ nhật cũng cạnh nguyên, chờ lâu một hồi Tichpx cứ thế cắt đôi và cắt đôi các hình chữ nhật tới khi tất cả các hình chữ nhật thành các hình vuông thì thôi. Tichpx biết rằng nếu hình chữ nhật ban đầu có cạnh là \(m * n\) thì cắt tối đa ra \(m*n\) hình vuông. Nhưng một câu hỏi đặt ra là muốn cắt ra ít nhất các hình vuông cạnh nguyên, có thể các hình vuông có các cạnh khác nhau miễn là vuông là được thì có bao nhiêu hình vuông là ít nhất. Biết rằng mỗi lần cắt là phải cắt thẳng và cắt rời thành hai hình

Bạn hãy lập trình tính giúp Tichpx nhé.

Input

Một dòng gồm hai số nguyên dương \(m,n (1 \le m,n \le 500)\).

Output

Một số nguyên dương duy nhất là số hình vuông ít nhất khi cắt hình chữ nhật \(m*n\).

Ví dụ 1

Input:

5 6

Output:

5

Ví dụ 2

Input:

99 100

Output:

12

Giải thích

Cắt hình chữ nhật 99*100

tichpx

Comments

There are no comments at the moment.