b590: 單位分數分解
標籤 :
通過比率 : 80% (4 人 / 5 人 ) (非即時)
評分方式:
Tolerant

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

內容

Unit Fraction Partition

輸入說明

測試檔包含多組測試資料,每一組測試資料都是四個正整數 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的方法(如上圖所示)

輸出說明

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

範例輸入
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
範例輸出
4
7
6
2
42
1
0
9
3
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (100%): 5.0s , <1K
提示 :
標籤:
出處:
SEARCC-ISSC國際學生程式設計競賽北京大學題庫 http://poj.org/problem?id=1980 [編輯:
spocktsai (囧rz)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」