1867.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1867 on 2006-08-30 at 16:47:42 */ 
#include <cstdio>
#include <algorithm>
using namespace std;
 
const int PN = 3200;
const int MC = 1 << 20;
const int MPR = 1024;
 
bool isPrime(int);
 
class TreeArray {
private:
	int in[MC];
	int lowBit(int t) const { return t&(-t); }
	int sum(int) const;
public:
	int C, chain[MC];
	bool isPrime[MC];
	void init(bool);
	int contain(int b, int e) const { return sum(e)-sum(b-1); }
	void add(int, int);
};
int TreeArray::sum(int n) const {
	int p = 0;
	while(n > 0) {
		p += in[n];
		n -= lowBit(n);
	}
	return p;
}
void TreeArray::init(bool pr) {
	for(int i = 1; i <= C; i++)
		if(pr) in[i] = lowBit(i);
		else in[i] = 0;
}
void TreeArray::add(int n, int m) {
	while(n <= C) {
		in[n] += m;
		n += lowBit(n);
	}
}
 
bool prime[PN];
int p[MPR], pn = 0;	
TreeArray ta;
 
int main()
{
	memset(prime, true, sizeof(prime));
	prime[0] = prime[1] = false;
	for(int i = 2; i < PN; i++) {
		if(!prime[i]) continue;
		p[pn++] = i;
		for(int j = 2; i*j < PN; j++) prime[i*j] = false;
	}
    for(int t = 1; ; t++) {
		int N, M;
        scanf("%d %d %d", &ta.C, &N, &M);
        if(ta.C == 0 && N == 0 && M == 0) return 0;
		printf("CASE #%d:\n", t);
		bool isP = isPrime(M);
		ta.init(isP);
		for(int i = 1; i <= ta.C; i++) {
			ta.chain[i] = M;
			ta.isPrime[i] = isP;
		}
		for(int i = 0; i < N; i++) {
			int o, x, y; scanf("%d %d %d", &o, &x, &y);
			if(o) printf("%d\n", ta.contain(x, y));
			else {
				ta.chain[x] += y;
				isP = isPrime(ta.chain[x]);
				if(isP != ta.isPrime[x]) {
					if(isP) ta.add(x, 1);
					else ta.add(x, -1);
					ta.isPrime[x] = isP;
				}
			}
		}
		putchar('\n');
    }
    
    return 0;
}
 
bool isPrime(int k)
{
	if(k < PN) return prime[k];
	for(int i = 0; i < pn; i++)
		if(k % p[i] == 0) return false;
	return true;
}