1923.cpp

HDOJ acm.hdu.edu.cn 第10卷的一些题目

//1923
#include <cstdio>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
const int NMAX = 2000000000;
const int SQRTNMAX  = 100000;//44750;
const int LENMAX = 50;
const int AMAX = 600;
const int BMIN = -560;
const int BMAX = 700;
int n,l,r,ans;
bool vis[SQRTNMAX];
int prime[10000],nprime;
int seq[300],nseq;
void cal_prime() {
	int i,j;
	nprime = 1;
	prime[0] = 2;
	for (i=3;i<SQRTNMAX;i+=2) {
		if (!vis[i]) {
			prime[ nprime++ ] = i;
			for (j=i+i;j<SQRTNMAX;j+=i) vis[j] = true;
		}
	}
}
bool is_prime(int p) {
	if (p < SQRTNMAX) {
		return ((p&1) && !vis[p]);
	}
	else {
		int i,rt = sqrt(1.0*p) +1;
		for (i=0;i<nprime && prime[i]<=rt;i++) {
			if (p%prime[i] == 0) return false;
		}
		return true;
	}
}
void cal() {
	int i,j,a,b,p;
	__int64 mul;
	int factor[LENMAX] = {1};
	for (a=1;a<=AMAX;a++) {
		for (b=3-a;b<=BMAX;b++) {
			mul = factor[1] = a+b;
			if (is_prime(factor[1])) {
				for (i=2;i<=LENMAX;i++) {
					factor[i] = a*factor[i-1] + b;
					mul *= factor[i];
					if (!is_prime(factor[i]) || mul > NMAX) break;
					if (i>=3) seq[ nseq++ ] = mul;
				}
			}
		}
	}
	sort(seq,seq+nseq);
}
int binary_find(int val) {
	int l = 0,r = nseq-1;
	int mid;
	while (l <= r) {
		mid = (l+r) / 2;
		if (seq[mid] == val) return mid;
		if (val < seq[mid]) r = mid -1;
		else l = mid +1;
	}
	return r;
}
int main() {
	int i,j;
	cal_prime();
	cal();
	scanf("%d",&n);
	while (n --) {
		scanf("%d %d",&l,&r);
		int lpos = binary_find(l);
		int rpos = binary_find(r);
		if (seq[lpos] < l || lpos < 0) lpos ++;
		ans = rpos - lpos +1;
		printf("%d\n",ans);
	}
}