Chiếc bánh của Harry
Xem dạng PDFĐêm Halloween, Harry Poster được một bà phù thủy tặng cho một chiếc bánh hình vuông có diện tích ban đầu là $A$. Vì muốn chia sẻ với bạn bè, Harry Poster đã cắt chiếc bánh nhiều lần để chia phần cho các bạn của cậu ấy.
Tuy nhiên, cậu muốn sau mỗi lần cắt, chiếc bánh của bản thân vẫn vuông vắn, nên mỗi lần cắt cậu quyết định cắt một nhát ngang và một nhát dọc, và mỗi nhát cắt của cậu đều làm giảm độ dài cạnh của chiếc bánh đi đúng 1 đơn vị. Nhưng ban đầu, chiếc bánh của bà phù thủy tặng cậu có thể không được hoàn hảo, tức là độ dài cạnh của chiếc bánh không nguyên, cho nên nhát cắt đầu tiên của cậu sẽ cắt đi phần dư nếu có.
Tốt là thế, nhưng Harry Poster vẫn muốn giữ lại một phần bánh có diện tích ít nhất bằng $B$ cho mình, cho nên cậu tự hỏi:
Liệu sau bao nhiêu lần cắt thì diện tích nhỏ nhất của phần bánh còn lại vẫn lớn hơn hoặc bằng $B$?
Yêu cầu: Bạn được cho $2$ số $A, B$, hãy trả lời câu hỏi của Harry Poster.
Dữ liệu vào
Nhập từ bàn phím:
- Một dòng duy nhất là $2$ số $A, B$ ($1 \le B \le A \le 2^{64}$)
Dữ liệu ra
Xuất ra màn hình:
- Một dòng duy nhất là yêu cầu của đề bài.
Ràng buộc
- Subtask $1$ ($30\%$): $A, B \le 10^{8}$
- Subtask $2$ ($30\%$): $A, B$ là số chính phương
- Subtask $3$ ($40\%$): Không ràng buộc gì thêm
Ví dụ
Input
10 1
Output
3
Giải thích
Ban đầu chiếc bánh có diện tích bằng $10$, cho nên cạnh có độ dài gần bằng $3.16$.
- Nhát cắt đầu tiên sẽ cắt đi phần dư $0.16$, diện tích còn lại $3 \times 3 = 9$.
- Nhát cắt thứ hai, diện tích còn lại $2 \times 2 = 4$
- Nhát cắt thứ 3, diện tích còn lại $1 \times 1 = 1$.
Không thể cắt nữa vì cắt nữa sẽ làm cho diện tích chiếc bánh bé hơn $B$.
Bình luận