Bear and Prime Numbers
题意翻译
给你一串数列a.对于一个质数p,定义函数f(p)=a数列中能被p整除的数的个数.给出m组询问l,r,询问[l,r]区间内所有素数p的f(p)之和.
题目描述
Recently, the bear started studying data structures and faced the following problem.
You are given a sequence of integers $ x_{1},x_{2},...,x_{n} $ of length $ n $ and $ m $ queries, each of them is characterized by two integers $ l_{i},r_{i} $ . Let's introduce $ f(p) $ to represent the number of such indexes $ k $ , that $ x_{k} $ is divisible by $ p $ . The answer to the query $ l_{i},r_{i} $ is the sum: , where $ S(l_{i},r_{i}) $ is a set of prime numbers from segment $ [l_{i},r_{i}] $ (both borders are included in the segment).
Help the bear cope with the problem.
输入输出格式
输入格式
The first line contains integer $ n $ $ (1<=n<=10^{6}) $ . The second line contains $ n $ integers $ x_{1},x_{2},...,x_{n} $ $ (2<=x_{i}<=10^{7}) $ . The numbers are not necessarily distinct.
The third line contains integer $ m $ $ (1<=m<=50000) $ . Each of the following $ m $ lines contains a pair of space-separated integers, $ l_{i} $ and $ r_{i} $ $ (2<=l_{i}<=r_{i}<=2·10^{9}) $ — the numbers that characterize the current query.
输出格式
Print $ m $ integers — the answers to the queries on the order the queries appear in the input.
输入输出样例
输入样例 #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
说明
Consider the first sample. Overall, the first sample has 3 queries.
1. The first query $ l=2 $ , $ r=11 $ comes. You need to count $ f(2)+f(3)+f(5)+f(7)+f(11)=2+1+4+2+0=9 $ .
2. The second query comes $ l=3 $ , $ r=12 $ . You need to count $ f(3)+f(5)+f(7)+f(11)=1+4+2+0=7 $ .
3. The third query comes $ l=4 $ , $ r=4 $ . As this interval has no prime numbers, then the sum equals 0.