#2967. 「COCI 2010.03.06」PROGRAM

内存限制:32 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Planet6174

题目描述

译自 COCI 2010.03.06 T5「PROGRAM

开始时, \mathit{seq} 数组已清零。请注意 \mathit{seq} 数组的第一个元素的下标是 0 而非 1。

void something (int jump) {
  for (int i = 0; i < N; i += jump)
    ++seq[i];
}

Mirko 调用了 \tt something 函数 K 次,第 i 次调用时 \tt jump= \it X_i

接下来有 Q 次查询,每次查询包含两个整数 L_i, R_i ,对于每组查询请输出 \displaystyle\sum_{i=L_i}^{R_i}\mathit{seq}_i

输入格式

第一行: N,K
接下来一行 K 个整数,第 i 个为 X_i
N+2 行: Q
接下来 Q 行:每行两个整数 L_i, R_i

输出格式

Q 行,第 i 行包含第 i 组查询的答案。

样例

样例输入 1

10 4
1 1 2 1
3
0 9
2 6
7 7

样例输出 1

35
18
3

样例说明 1

seq=\{4, 3, 4, 3, 4, 3, 4, 3, 4, 3\}

样例输入 2

11 3
3 7 10
3
0 10
2 6
7 7

样例输出 2

8
2
1

样例说明 2

seq=\{3, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1\}

样例输入 3

1000000 6
12 3 21 436 2 19
2
12 16124
692 29021

样例输出 3

16422
28874

数据范围与提示

1≤N,K,Q≤10^6, 1≤X_i<N, 0≤L_i≤R_i<N .