← 返回题目列表

Codeforces · 385/C

C. 熊数和素数

中文机器翻译题面 查看原题

最近,小熊开始学习数据结构,面临以下问题。

给定一个长度为 n 和 m 个查询的整数 x1、x2、...、xn 序列,每个查询都由两个整数 li、ri 来表征。我们引入 f(p) 来表示此类索引 k 的数量,即 xk 可以被 p 整除。查询 li, ri 的答案是总和:$$\sum_{p \in S(l_i, r_i)} f(p)$$,其中 S(li, ri) 是段 [li, ri] 中的一组素数(两个边界都包含在该段中)。

帮助熊解决问题。

输入

第一行包含整数 n (1 ≤ n ≤ 106)。第二行包含 n 个整数 x1, x2, ..., xn (2 ≤ xi ≤ 107)。这些数字不一定是不同的。

第三行包含整数 m (1 ≤ m ≤ 50000)。以下 m 行中的每一行都包含一对空格分隔的整数 li 和 ri (2 ≤ li ≤ ri ≤ 2·109) — 表征当前查询的数字。

输出

打印 m 个整数 — 按照查询在输入中出现的顺序查询查询的答案。

示例

输入 #1

6
5 5 7 10 14 15
3
2 11
3 12
4 4

输出 #1

9
7
0

输入 #2

7
2 3 5 7 11 4 8
2
8 10
2 123

输出 #2

0
7

注意

考虑第一个样本。总的来说,第一个样本有 3 个查询。

1. 第一个查询 l = 2, r = 11 出现。您需要计算 f(2) + f(3) + f(5) + f(7) + f(11) = 2 + 1 + 4 + 2 + 0 = 9。
2、第二个查询是l = 3,r = 12,需要数f(3) + f(5) + f(7) + f(11) = 1 + 4 + 2 + 0 = 7。
3. 第三个查询是l = 4,r = 4,由于这个区间没有素数,所以和等于0。