問題一覧 > 通常問題

No.2758 RDQ

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

    問題文

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

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

    • 入力

    NN QQ  
A1A_1 …\dots ANA_N  
L1L_1 R1R_1 K1K_1  
⋮\vdots  
LQL_Q RQR_Q KQK_Q
    • 2≤N≤5×1042\le N\le 5\times 10^4
    • 1≤Q≤5×1041\le Q\le 5\times 10^4
    • 1≤Ai≤1051\le A_i\le 10^5
    • 1≤Lj<Rj≤N (1≤j≤Q)1\le L_j\lt R_j\le N\ (1\le j\le Q)
    • 1≤Kj≤1051\le K_j\le 10^5
    • 入力はすべて整数

    出力

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

    サンプル

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

    11 個目の質問では A1,A2,A3,A4A_1,A_2,A_3,A_4 のうち A1=2,A2=6A_1=2,A_2=6 が条件を満たします。よって 22 を出力します。
    また 22 個目の質問では A3,A4,A5A_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もしくは右上の雲マークをクリックしてアカウントを作成してください。