Multiple of k

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Multiple of k

本题是 P1306 的多组询问版,建议先通过P1306后再尝试本题。

时间限制:3s

空间限制:256MB

题目描述

现有长度为 nn 的数列 aa ,给定正整数 kk ,请回答 qq 次询问,每次询问给定 L,RL,R,求所有的二元组(i, j)(i,\ j)的个数,使得:

  • LijRL\le i\le j\le R
  • ai+ai+1+..+aja_i+a_{i+1}+..+a_jkk 的倍数

输入格式

第一行三个正整数 n,k,qn,k,q

接下来一行包含 nn 个整数,表示这个数列。

接下来 qq 行每行两个整数 L,RL, R,表示一次询问

输出格式

qq 行,每行一个正整数,表示满足条件的二元组的个数。

样例输入1

8 2 6
1 1 1 0 1 0 1 1
1 4
1 3 
2 4
1 1
2 2
3 8

样例输出1

4
2
3
0
0
9

样例输入2

52 3 61
2 2 1 1 2 0 2 2 0 0 1 1 0 2 1 2 1 1 1 1 0 1 1 2 1 0 0 2 2 0 0 2 0 2 1 2 2 1 1 0 0 0 0 2 1 0 0 0 2 0 0 0 
8 28
9 13
10 30
27 42
20 30
18 26
38 52
7 45
42 42
23 39
17 19
36 45
18 47
21 23
3 24
17 37
21 29
11 45
3 12
34 43
16 22
48 49
50 52
2 24
33 41
12 12
41 44
15 31
8 41
18 46
23 26
24 45
17 46
30 39
11 40
44 47
12 31
4 20
11 35
7 13
25 30
12 13
14 33
19 44
49 51
30 44
32 36
19 31
27 42
21 48
1 49
18 51
20 42
9 20
7 14
12 16
35 40
1 2
28 46
13 30
43 45

样例输出2

72
4
71
48
19
12
51
263
1
49
1
24
169
1
78
72
12
217
15
24
8
1
6
87
18
0
6
48
195
154
4
99
169
15
151
6
70
48
106
7
5
1
70
121
3
40
4
26
48
156
413
212
96
22
9
6
6
0
71
55
3

数据范围及限制

1n,q2105,1k5105,0ai<k1\le n, q\le 2*10^5, 1\le k \le 5*10^5, 0\le a_i<k

请注意,答案可能不在3232位整数范围内。

2022迎新春赛

未参加
状态
已结束
规则
ACM/ICPC
题目
8
开始于
2022-01-31 08:00
结束于
2022-02-06 08:00
持续时间
144.0 小时
主持人
参赛人数
90