首页 > 代码库 > Codeforces Round #226 (Div. 2) C
Codeforces Round #226 (Div. 2) C
题目:
CF机子真心强大啊,这样才跑了600ms,给了你n个数的序列,然后m次询问,每次询问求出序列中每个数是 区间[a,b]内的 几个素数的倍数统计一下,然后对于个数求和,看了题目下面的hint很易懂,然后看到a,b的范围有些大哈,2*10^9,不知道怎么处理,但是后来发现,序列中的数 最大为10^7,所以就算a,b,再大也无所谓的,大于序列中的最大数的部分的素数,序列中不会有任何数 是它倍数的,然后就是对10^7以内的 素数进行预处理,同时把序列中的数统计一下个数,在预处理素数的同时 会有一个筛选祛除 该素数倍数的过程,就在这里判断一下该素数的倍数是否在序列中,若在就加上该数的个数,最后求一下前缀和,然后 答案就是 sum[b] - sum[a - 1]了,
在筛选素数的时候 第二个for循环一般都是 从2*i,开始的,但是 不保证序列中没有素数哈,比如说第一个案例,序列中有5,那么5是5的倍数,如果第二层循环从2*i开始就会漏掉一部分,这里习惯性的写法,让我卡了一会,因为 那里调试不太好弄,
int n; int nnum[10000000 + 55]; bool isprime[10000000 + 55]; int prime[10000000 + 55]; int k; void get_prime() { memset(isprime,false,sizeof(isprime)); for(int i=2;i<10000005 ;i++) { if(!isprime[i]) for(int j=i /*2 * i*/;j<10000005;j+=i) { isprime[j]=true; if(nnum[j])prime[i] += nnum[j]; } } //for(int i=2;i<1000005;i++) // if(!isprime[i]) // prime[k++]=i; for(int i=1;i<10000005;i++) prime[i] += prime[i - 1]; } void init() { memset(prime,0,sizeof(prime)); memset(nnum,0,sizeof(nnum)); } bool input() { while(cin>>n) { for(int i=0;i<n;i++) { int x; scanf("%d",&x); nnum[x]++; } return false; } return true; } void cal() { get_prime(); int m; scanf("%d",&m); while(m--) { int a,b; scanf("%d %d",&a,&b); a = a>10000000?10000000:a; b = b>10000000?10000000:b; printf("%d\n",prime[b] - prime[a - 1]); } } void output() { } int main() { while(true) { init(); if(input())return 0; cal(); output(); } return 0; }
Codeforces Round #226 (Div. 2) C
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。