[duyhung123abc]

Đây là đáp án của bài chocolate

_ Giả sử ta muốn cắt hình chữ nhật kích thước LxW thành hình chữ nhật kích thước AxB. Nếu hình chữ nhật AB có thể nằm trong hình chữ nhật LW thì ta chỉ cần tối đa 2 lần cắt. Nếu hcn AB bằng hcn LW thì không cần lần cắt nào, nếu cạnh nhỏ của AB bằng cạnh nhỏ của LW hoặc cạnh lớn của LW bằng cạnh lớn của AB thì ta chỉ cần 1 lần cắt.

_ Vậy ta chỉ kiểm tra lần lượt các hình chữ nhật có diện tích AxB = S, tương đương với việc phân tích S thành tích của 2 số A và B. Cách làm bình thường là ta duyệt A từ 1 đến (S/2), nếu S chia hết cho A thì ta gán B:=S div A và kiểm tra như trên. Nhưng ở đây S có thể lên tới 10^9 nên ta phải cải tiến chỉ duyệt A từ 1 đến sqrt(S).