首页 > 代码库 > 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