Multiple of k
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Multiple of k
本题是 P1306 的多组询问版,建议先通过P1306后再尝试本题。
时间限制:3s
空间限制:256MB
题目描述
现有长度为 \(n\) 的数列 \(a\) ,给定正整数 \(k\) ,请回答 \(q\) 次询问,每次询问给定 \(L,R\),求所有的二元组\((i,\ j)\)的个数,使得:
- \(L\le i\le j\le R\)
- \(a_i+a_{i+1}+..+a_j\)是 \(k\) 的倍数
输入格式
第一行三个正整数 \(n,k,q\)
接下来一行包含 \(n\) 个整数,表示这个数列。
接下来 \(q\) 行每行两个整数 \(L, R\),表示一次询问
输出格式
共 \(q\) 行,每行一个正整数,表示满足条件的二元组的个数。
样例输入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
数据范围及限制
\(1\le n, q\le 2*10^5, 1\le k \le 5*10^5, 0\le a_i<k\)
请注意,答案可能不在\(32\)位整数范围内。