d013. 單位分數 - TCFSH's Online Judge System

內容

所謂單位分數是指分子為1、分母為正整數的分數。一個有理數p/q可以表示成數個單位分數的和，例如2/3可以表示成2/3=1/2+1/6。(1/2與1/6順序對調視為相同)。給定四個正整數p、q、a、n，求出p/q在滿足底下二種條件下，有幾種單位分數的組合。

A.分數最多由n個單位分數所組成。

B.所有單位分數的分母的積，不可大於a。(可以等於a)

例如，若(p，q，a，n)= (2，3，120，3)，則共有4種單位分數的組合，可以等於2/3。

2/3=1/3+1/3

=1/2+1/6

=1/4+1/4+1/6

=1/3+1/6+1/6

輸入說明

每一列共有四個數字p、q、a、n，而p，q<=800、a<=12000、n<=7，四個整數彼此以空格分開。

輸出說明

在滿足題目內第A、B條件限制下，單位分數的組合數。

範例輸入 #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

範例輸出 #1

測資資訊：

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

提示：

標籤:

出處:

ISSC 2010模擬賽8A [管理者：

franklin (管理員)

]

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