回『競賽題庫』
c009: 5. P⼒量
標籤 :
通過比率 : 3人/10人 ( 30% ) [非即時]
評分方式：
Tolerant

最近更新 : 2024-07-31 18:56

內容

⼀個序列與⼀個質數之間會產⽣⼀股⼒量，稱之為 P ⼒量。若序列中有 K 個數字能夠被那個質數整除的話，則它們之間的 P ⼒量就是 K。 史密斯是⼀名專攻 P ⼒量的⼤博⼠，有⼀天他發現了⼀個序列 S。為了研究這個序列，史密斯決定調查這個序列的⼀些連續⼦序列，S[L1, R1], S[L1, R1],..., S[LQ, RQ] 與某些質數 P1, P2,..., PQ 之間產⽣的⼒量為多少。為了⽅便起⾒，這些⼦序列的左界與右界分別都會單調遞增。也就是說，L1 ≤ L2 ≤ ... ≤ LQ-1 ≤ LQ 且 R1 ≤ R2 ≤ ... ≤ RQ-1 ≤ RQ。

以下圖為例：

序列 (1, 2, 3, 4) 與質數 2 之間的 P ⼒量為 2，因為這個序列中有兩個元素可以被 2 整除。

輸入說明

輸入的第⼀⾏會包含⼀個整數 T，代表測資數量。

每筆測資的第⼀⾏會有兩個整數 N, Q，代表序列的長度與詢問的數量。

每筆測資的第⼆⾏會有 N 個整數 S1, S2,..., SN，代表序列中的元素。

每筆測資接下來的 Q ⾏，每⾏會有三個整數 Li, Ri, Pi，代表史密斯想要知道 S[Li, Ri] 所構成的⼦序列與 Pi 之間的 P ⼒量為多少。

輸出說明

對於每筆詢問，輸出⼀個整數代表那個⼦序列與那個質數之間的 P ⼒量。

範例輸入 #1 
1
4 5
1 2 3 4
1 2 2
1 3 3
1 4 2
2 4 5
3 4 2
範例輸出 #1 
1
1
2
0
1
範例輸入 #2 
2
5 3
2 2 2 2 2
1 1 2
1 3 3
2 5 7
4 3
3 6 9 12
1 2 2
2 3 3
2 4 2
範例輸出 #2 
1
0
0
1
2
2
範例輸入 #3 
1
6 5
2 6 30 210 2310 30030
2 3 3
3 4 5
4 5 7
5 6 11
6 6 13
範例輸出 #3 
2
2
2
2
1
測資資訊：
記憶體限制： 512 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1K
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
提示 ：
標籤:
出處:
2022YTP初賽 [管理者：
zero (管理員)
]

本題狀況 本題討論 排行

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