b590: 單位分數分解
Tags :
Accepted rate : 7人/8人 ( 88% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-10-21 13:29

Content

Unit Fraction Partition

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
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
4
7
6
2
42
1
0
9
3
測資資訊:
記憶體限制: 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
沒有發現任何「解題報告」