Ở Ai Cập cổ đại, người ta sử dụng tổng các phân số đơn vị (có dạng , với là số tự nhiên) để biểu diễn mọi số hữu tỉ. Ví dụ: , nhưng không cho phép vì các số hạng trong tổng có mẫu số giống nhau.
Đối với một phân số , có rất nhiều cách biểu diễn, nhưng cách nào là tốt nhất?
Tiêu chí đánh giá như sau:
Số lượng số hạng ít hơn thì tốt hơn.
Nếu số lượng số hạng bằng nhau, phân số nhỏ nhất trong tổng càng lớn càng tốt (tức là mẫu số của phân số cuối cùng càng nhỏ càng tốt).
Ví dụ:
Cách tốt nhất là cách cuối cùng, vì lớn hơn .
Lưu ý, có thể có nhiều lời giải tối ưu. Ví dụ:
Do cả hai cách đều có phân số nhỏ nhất giống nhau, nên cả hai đều là lời giải tối ưu.
Cho , hãy lập trình tính toán cách biểu diễn tốt nhất. Đảm bảo lời giải tối ưu thỏa mãn: phân số nhỏ nhất .
Dữ liệu:
Một dòng chứa hai số nguyên, lần lượt là giá trị của và .
Kết quả:
Xuất ra một vài số, sắp xếp từ nhỏ đến lớn, lần lượt là mẫu số của các phân số đơn vị.
