Recently, the bear started studying data structures and faced the following problem.
You are given a sequence of integers x1, x2, ..., xn of length n and m queries, each of them is characterized by two integers li, ri. Let's introduce f(p) to represent the number of such indexes k, that xk is divisible by p. The answer to the query li, ri is the sum: , where S(li, ri) is a set of prime numbers from segment [li, ri] (both borders are included in the segment).
Help the bear cope with the problem.
Input
The first line contains integer n (1 ≤ n ≤ 106). The second line contains n integers x1, x2, ..., xn (2 ≤ xi ≤ 107). 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, li and ri (2 ≤ li ≤ ri ≤ 2·109) — the numbers that characterize the current query.
Output
Print m integers — the answers to the queries on the order the queries appear in the input.
Example
6
5 5 7 10 14 15
3
2 11
3 12
4 4
9
7
0
7
2 3 5 7 11 4 8
2
8 10
2 123
0
7
Note
Consider the first sample. Overall, the first sample has 3 queries.
- 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.
- 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.
- The third query comes l = 4, r = 4. As this interval has no prime numbers, then the sum equals 0.
题意:给n个数,给出m组l,r.设i为l-r之间的一个质数,这个质数能被n个数中的x个数整除,令f(i)=x.求l-r区间中所有f(i)的总和.
思路:首先考虑暴力做法,筛出1-10000000质数,然后用n个数除以l-r内的所有质数,加起来求出答案.复杂度很高,尤其是使用O(n√n)的滑稽筛法.这里可以用埃氏筛来筛质数,复杂度O(nloglogn).由于l-r有重复,所以可以事先记录,用前缀和进行优化,复杂度仍不过关,因为遍历n的复杂度仍太高.这时候可以用一些埃氏筛的美妙性质:
for(i=;i<N;i++)
{
if(!vis[i])
{
for(j=i;j<N;j+=i)
{
vis[j]=;
}
}
}
上图是一个埃氏筛的模板,我们发现当i是质数时,该程序会遍历所有i的倍数,如果我们开一个数组cnt,cnt[i]记录n中第i个数出现的数量.若j扫到cnt[j]>0,sum[i]+=cnt[j](就是有新的cnt[j]个数能整除i)
for(i=;i<N;i++)
{
if(!vis[i])
{
for(j=i;j<N;j+=i)
{
if(cnt[j])
{
sum[i]+=cnt[j];
}
vis[j]=;
}
}
}
就这么简单!
但这样竟然还是RE了,smg?!
仔细看题目,你会发现,尼玛l,r<=2*10^9....
数组开小了!
那么是滑稽的开2*10^9然后拿MLE回家还是再优化?
我们发现sum[r](r>10^7)的值和sum[10^7]有区别吗....
显然是没有的,因为不存在比10^7大的n.
所以就在优化一下了~
最后代码:
#include<cstdio>
#define N 10000010
using namespace std; int k,cnt[N],vis[N],sum[N],n,i,j; int main()
{
scanf("%d",&n);
for(i=;i<=n;i++)
{
scanf("%d",&k);
cnt[k]++;
}
for(i=;i<N;i++)
{
if(!vis[i])
{
for(j=i;j<N;j+=i)
{
if(cnt[j])
{
sum[i]+=cnt[j];
}
vis[j]=;
}
}
}
for(i=;i<=N;i++)
{
sum[i]+=sum[i-];
}
int t,l,r;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&l,&r);
if (l>N)
{
l=N-;
}
if (r>N)
{
r=N;
}
long long ans=sum[r]-sum[l-];
printf("%lld\n",ans);
}
}
每天刷题,身体棒棒!