codeforces 385C Bear and Prime Numbers

codeforces 385C 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} 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#include#define N 10000010#includeusing 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;}templateinline 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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。