| Source : HCPC 2005 Spring | |||
| Time limit : 2 sec | Memory limit : 32 M | ||
Submitted : 2521, Accepted : 594
输入格式
题目有多组输入。每组输入第一行有三个整数：C 连锁店的数量 N 指令的条数 M 每家连锁店初始的商品数量
接下来有N行，每行有一条指令。指令的格式为：
0 x y 连锁店x的商品数量变化值为y，y > 0商品数量增加， y < 0减少
1 i j 输出编号在[i,j]区间内的连锁店中商品数量为素数的有多少家
1 <= i, x, j < 1000000 连锁店中的商品数量a满足 0 <= a < 10000000，C = N = M = 0标志输入结束
输出格式
对于每组输入，输出它的序号。对于一组输入中的1指令输出要求的整数。每组输出后打印一行空行。
样例输入
100000 4 4 0 1 1 1 4 10 0 11 3 1 1 11 20 3 0 1 1 20 0 3 3 1 1 20 0 0 0样例输出
CASE #1: 0 2 CASE #2: 0 1
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <iomanip>
#define INF 99999999
typedef long long LL;
using namespace std;
const int MAX=1000000+10;
int n,m,q;
int a[MAX],c[MAX];
bool prime[MAX*10];
void Prime(){
prime[0]=prime[1]=true;
for(int i=2;i*2<=10000000;++i)prime[i*2]=true;
for(int i=3;i*i<=10000000;i+=2){
if(!prime[i]){
for(int j=i*i;j<=10000000;j+=2*i)prime[j]=true;
}
}
}
int lowbit(int x){
return x&(-x);
}
void Update(int x,int y){
while(x<=n){
c[x]+=y;
x+=lowbit(x);
}
}
int Query(int x){
int sum=0;
while(x>0){
sum+=c[x];
x-=lowbit(x);
}
return sum;
}
int main(){
Prime();
int op,x,y,k,p,num=0;
while(scanf("%d%d%d",&n,&q,&m),n+q+m){
p=prime[m]?0:1;
for(int i=1;i<=n;++i)a[i]=m;
for(int i=1;i<=n;++i){
k=lowbit(i);
c[i]=k*p;
}
printf("CASE #%d:\n",++num);
for(int i=0;i<q;++i){
scanf("%d%d%d",&op,&x,&y);
if(op == 0){
a[x]+=y;
if(!prime[a[x]] && prime[a[x]-y])Update(x,1);
if(prime[a[x]] && !prime[a[x]-y])Update(x,-1);
}
else printf("%d\n",Query(y)-Query(x-1));
}
printf("\n");
}
return 0;
}
原文：http://blog.csdn.net/xingyeyongheng/article/details/20789139