b590. 單位分數分解 - 高中生程式解題系統

Content

Input

測試檔包含多組測試資料，每一組測試資料都是四個正整數 p, q, a, n，其中 n, p, q <= 800, a <= 12000 且 n <= 7。
請找出有多少組可能的分解，可以將 p/q 分解成 n 個以內的單位分數，每個單位分數的分母小於等於 a。
遇到輸入 0 0 0 0 就結束

例如題目的例子 2 3 120 3，就有四種將 2/3 分解成3個分母小於等於120的方法(如上圖所示)

Output

對於每一組測試資料輸出可以有多少組 n 個以內的單位分數相加的組合，滿足單位分數分母都小於等於 a

Sample Input #1

2 3 120 3
2 3 300 3
2 3 299 3
2 3 12 3
2 3 12000 7
54 795 12000 7
2 3 300 1
2 1 200 5
2 4 54 2
0 0 0 0

Sample Output #1

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (100%): 5.0s , <1K

Hint ：

Tags:

出處:

SEARCC-ISSC國際學生程式設計競賽北京大學題庫 http://poj.org/problem?id=1980 [管理者： spocktsai (囧rz) ]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」