#15 Multiple count

難易度

## 問題 長さ$N$の数列$A$及び整数$K$が与えられます。 $Q$個の以下のクエリに答えてください。 - $i(1 \le i \le Q)$個目のクエリでは整数$X_i$及び$Y_i$が与えられるので、数列$A$の$X_i$番目から$Y_i$番目(両端を含む)にある$K$の倍数の個数を出力してください。 ## 入力 $N \hspace{7pt} K$ $A_1 \hspace{7pt} A_2 \hspace{7pt} A_3 \hspace{5pt} \dots \hspace{5pt} A_N$ $Q$ $X_1 \hspace{7pt} Y_1$ $X_2 \hspace{7pt} Y_2$ $X_3 \hspace{7pt} Y_3$ $\hspace{14pt} \vdots$ $X_Q \hspace{7pt} Y_Q$ ## 制約 $1 \le N \le 10^6$ $ 1\le K \le 10^9$ $1 \le A_i \le 10^9$ $1 \le Q \le 10^6$ $1 \le X_i \le Y_i \le N(1\le i \le Q)$ ## 例 ### 入力例1 ``` 4 4 1 8 16 6 3 1 3 1 1 3 4 ``` ### 出力例1 ``` 2 0 1 ``` 一個目のクエリでは数列の1番目から3番目、つまり1,8,16の中に$K(=4)$の倍数は2個(8と16)あるので2を出力します。 二個目のように範囲がちょうど1個だけの数字を指していたり、$K$の倍数が一個もない場合があります。