http://www.elijahqi.win/archives/2940
题意翻译
给你一串数列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}
x1,x2,…,xn of length
n
n and
m
m queries, each of them is characterized by two integers
l_{i},r_{i}
li,ri . Let’s introduce
f(p)
f(p) to represent the number of such indexes
k
k , that
x_{k}
xk is divisible by
p
p . The answer to the query
l_{i},r_{i}
li,ri is the sum: , where
S(l_{i},r_{i})
S(li,ri) is a set of prime numbers from segment
[l_{i},r_{i}]
[li,ri] (both borders are included in the segment).
Help the bear cope with the problem.
输入输出格式
输入格式：
The first line contains integer
n
n
(1<=n<=10^{6})
(1<=n<=106) . The second line contains
n
n integers
x_{1},x_{2},…,x_{n}
x1,x2,…,xn
(2<=x_{i}<=10^{7})
(2<=xi<=107) . The numbers are not necessarily distinct.
The third line contains integer
m
m
(1<=m<=50000)
(1<=m<=50000) . Each of the following
m
m lines contains a pair of space-separated integers,
l_{i}
li and
r_{i}
ri
(2<=l_{i}<=r_{i}<=2·10^{9})
(2<=li<=ri<=2⋅109) — the numbers that characterize the current query.
输出格式：
Print
m
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.
The first query
l=2
l=2 ,
r=11
r=11 comes. You need to count
f(2)+f(3)+f(5)+f(7)+f(11)=2+1+4+2+0=9
f(2)+f(3)+f(5)+f(7)+f(11)=2+1+4+2+0=9 .
The second query comes
l=3
l=3 ,
r=12
r=12 . You need to count
f(3)+f(5)+f(7)+f(11)=1+4+2+0=7
f(3)+f(5)+f(7)+f(11)=1+4+2+0=7 .
The third query comes
l=4
l=4 ,
r=4
r=4 . As this interval has no prime numbers, then the sum equals 0.
根据数学公式暴力
预处理sum表示前i个质数他可能被哪些数整除 的个数 先线性筛一下 然后暴力统计预处理前缀和
#include<cstdio>#include<cctype>
#define N 10000010
#include<algorithm>
using namespace std;
inline char gc(){
static char now[1<<16],*S,*T;
if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
return *S++;
}
inline int read(){
int x=0,f=1;char ch=gc();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=gc();}
while(isdigit(ch)) x=x*10+ch-'0',ch=gc();
return x*f;
}
const int out_len=1<<16;
char obuf[out_len],*oh=obuf;
inline void write_char(char c){
if (oh==obuf+out_len) fwrite(obuf,1,out_len,stdout),oh=obuf;
*oh++=c;
}
template<class T>
inline void W(T x){
static int buf[30],cnt;
if(!x) write_char('0');else{
if (x<0) write_char('-'),x=-x;
for (cnt=0;x;x/=10) buf[++cnt]=x%10+48;
while(cnt) write_char(buf[cnt--]);
}
}
inline void flush(){fwrite(obuf,1,oh-obuf,stdout);}
int n,a[N/10],prime[N],tot,sum[N],cnt[N];bool not_prime[N];
int main(){
freopen("cf385c.in","r",stdin);
n=read();for (int i=1;i<=n;++i) a[i]=read(),++cnt[a[i]];
for (int i=2;i<=1e7;++i){
if(!not_prime[i]) prime[++tot]=i;
for (int j=1;prime[j]*i<=1e7;++j){
not_prime[prime[j]*i]=1;
if (i%prime[j]==0) break;
}
}
for (int i=1;i<=tot;++i)
for (int j=1;j*prime[i]<=1e7;++j) sum[i]+=cnt[j*prime[i]];
for (int i=1;i<=tot;++i) sum[i]+=sum[i-1];
int m=read();
for (int i=1;i<=m;++i){static int l,r;
l=lower_bound(prime+1,prime+tot+1,read())-prime-1;
r=upper_bound(prime+1,prime+tot+1,read())-prime-1;
// printf("%d\n",sum[r]-sum[l]);
W(sum[r]-sum[l]);write_char('\n');
}flush();
return 0;
}