b619. 三元組 (triples) - Online Judge System

Content

小 K 的數學作業當中有這樣一道題：
• 給定一個正整數 n，求所有的三元組 (x,y,z)，使得 ax+by+cz=n。其中，x,y,z 須為正整數。
小 K 認為這道題太簡單了。於是，他找到了老師並讓他把題目加難。思考片刻後，老師決定把題目改成以下的困難版本：
• 給定一個正整數 n，求所有的三元組 (x,y,z)，使得 ax+by+cz≤n。其中，x,y,z 須為非負整數。
但在小 K 解題之前，他希望你能幫他找出滿足條件的三元組的個數，令他能在作業簿上提前預留足夠的空間寫下答案。
當然，小 K 希望把簡單版本和困難版本的題目都解決。具體地，他會使用一個正整數 m 告知你需要回答哪個版本的答案。若 m=1，你需要回答簡單版本的題目中滿足條件的三元組的個數；若 m=2，你需要回答困難版本的題目中滿足條件的三元組的個數。

Input

你需要在標準輸入 (stdin) 讀入數據。
本題有多組測試數據。
輸入的第一行包含一個正整數 T，表示測試數據組數。
對於每組測試數據：
• 僅含一行，包含五個正整數 n,m,a,b,c，以空格分隔。

Output

你需要在標準輸出 (stdout) 輸出答案。
對於每組測試數據：
• 輸出一行，一個整數表示答案。

Sample Input #1

2
8 1 1 2 2
8 2 1 2 2

Sample Output #1

3
55

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (4%): 2.0s , <1K
公開測資點#1 (4%): 2.0s , <1K
公開測資點#2 (4%): 2.0s , <1K
公開測資點#3 (4%): 2.0s , <1K
公開測資點#4 (4%): 2.0s , <1K
公開測資點#5 (4%): 2.0s , <1K
公開測資點#6 (4%): 2.0s , <1K
公開測資點#7 (4%): 2.0s , <1K
公開測資點#8 (4%): 2.0s , <1K
公開測資點#9 (4%): 2.0s , <1K
公開測資點#10 (4%): 2.0s , <1K
公開測資點#11 (4%): 2.0s , <1K
公開測資點#12 (4%): 2.0s , <1K
公開測資點#13 (4%): 2.0s , <1K
公開測資點#14 (4%): 2.0s , <1K
公開測資點#15 (4%): 2.0s , <1K
公開測資點#16 (4%): 2.0s , <1K
公開測資點#17 (4%): 2.0s , <1K
公開測資點#18 (4%): 2.0s , <1K
公開測資點#19 (4%): 2.0s , <1K
公開測資點#20 (4%): 2.0s , <1K
公開測資點#21 (4%): 2.0s , <1K
公開測資點#22 (4%): 2.0s , <1K
公開測資點#23 (4%): 2.0s , <1K
公開測資點#24 (4%): 2.0s , <1K

Hint ：

【樣例1 解釋】
對於第一組數據：滿足條件的三元組有 (2,1,2),(2,2,1),(4,1,1)，共 3 個。
對於第二組數據：共有 55 個互不相同的三元組滿足條件。

【數據範圍】
對於所有測試數據，保證：
• T≤5
• n≤min{10^6,8000a,8000b,8000c}
• m≤2
• a,b,c≤1000

特殊性質 A：a=b=c。

Tags:

出處:

[管理者：

ricky (電腦黃)

]

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