r872. PA. 桿 - 高中生程式解題系統

內容

製作細長棒材的過程如下：

選擇一根桿子作為底座。可用的桿長度為：A_1, ... , A_N 。
將桿件 0 增加或更多，直到達到所需長度。如果透過將機器設定為大於或等於 2 和 k 的正整數來輸入桿件，則長度為 x 的桿件將變為長度為 kx 的桿件。

對於給定的每個 Q 個長度，輸出建立長度為 L_i 的條形的方法數。如果兩種方法不同，則表示最初選擇的條形不同，或在條形增長過程中輸入的整數序列 k 不同。

輸入說明

第一行包含長條圖的數量 N (1 <= N <= 100000)

第二行包含 N 個不同的整數 A_1, A_2, ... , A_N ，它們之間以空格分隔。 (1 <= A_i <= 100000)

第三行表示要建立的條形數量 Q 。 (1 <= Q <= 100000)

第四行包含 Q 個整數 L_1, ... , L_Q ，以空格分隔。 (1 <= L_i <= 100000)

輸出說明

在第一行列印 Q 個數字，數字之間以空格分隔。第 i 個數字表示製作長度為 L_i 的桿的方法數。保證所有可能的輸入，答案不超過 10^9 。

範例輸入 #1

5
1 2 3 4 5
6
1 2 3 4 5 6

範例輸出 #1

1 2 2 4 2 5

測資資訊：

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

提示：

以下是建立長度為 6 的長條圖的不同方法：：

選擇一根長度為 1 的桿。將其長度增加成 2 倍，使其長度變成 2 。將其長度增加成 3 倍，使其長度變成 6 。
選擇一根長度為 1 的桿。將其長度增加成 3 倍，使其長度變成 3 。將其長度增加成 2 倍，使其長度變成 6 。
選擇一根長度為 1 的桿。將其長度增加成 6 倍，使其長度變成 6 。
選擇一根長度為 2 的桿。將其長度增加成 3 倍，使其長度變成 6 。
選擇一根長度為 3 的桿。將其長度增加成 2 倍，使其長度變成 6 。

標籤:

DP contest Zaim

出處:

[管理者：

chenwei98050 ... (陳維（Z）) ]

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