問題一覧 > 通常問題

No.2758 RDQ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 98
作問者 : matcharate12 / テスター : 👑 binap aplysiaSheep
4 ProblemId : 7057 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-05-17 22:25:08
追記
  • 22:24　問題文の紛らわしい箇所を訂正しました。
    • Story
    ラテ君は $N$ 人の友達がおり、そのうちいくつかの人は、ラテ君の好きな整数倍の数値が書かれたカードを持っています。このカードを持っている人は、皆ラテ君の親友らしいです。
    果たしてそれは、特定の区間に注目したとき何人の親友がいるのでしょうか？

    問題文

    長さ $N$ の数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます。この数列において以下のような質問が $Q$ 個与えられるので、順に処理してください。

  • 区間 $[L,R]$ の要素 $A_L,A_{L+1},...,A_R$ において、$K$ の倍数である整数である要素はいくつありますか？

    • 入力

    $N$ $Q$  
$A_1$ $\dots$ $A_N$  
$L_1$ $R_1$ $K_1$  
$\vdots$  
$L_Q$ $R_Q$ $K_Q$
    • $2\le N\le 5\times 10^4$
    • $1\le Q\le 5\times 10^4$
    • $1\le A_i\le 10^5$
    • $1\le L_j\lt R_j\le N\ (1\le j\le Q)$
    • $1\le K_j\le 10^5$
    • 入力はすべて整数

    出力

    $Q$ 行出力してください。$j$ 行目には $j$ 個目の質問の答えを出力してください。

    サンプル

    サンプル1
    入力
    5 3
2 6 7 19 14
1 4 2
3 5 4
1 5 7
    出力
    2
0
2

    $1$ 個目の質問では $A_1,A_2,A_3,A_4$ のうち $A_1=2,A_2=6$ が条件を満たします。よって $2$ を出力します。
    また $2$ 個目の質問では $A_3,A_4,A_5$ のうち条件を満たすものは存在しません。

    サンプル2
    入力
    5 4
7 6 5 4 3
1 5 2
2 3 3
2 4 4
1 3 5
    出力
    2
1
1
1

    サンプル3
    入力
    3 1
1000 1000 100
1 3 10
    出力
    3

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。