http://acm.hit.edu.cn/hoj/problem/view?id=1867
| Source : HCPC 2005 Spring | |||
| Time limit : 2 sec | Memory limit : 32 M | ||
Submitted : 2994, Accepted : 686
输入格式
题目有多组输入。每组输入第一行有三个整数：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<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 1000010;
int n , val;
int num[MAXN];
int treeNum[MAXN];
int lowbit(int x){
return x&(-x);
}
int getSum(int x){
int sum = 0;
while(x){
sum += treeNum[x];
x -= lowbit(x);
}
return sum;
}
void add(int x , int val){
while(x < MAXN){
treeNum[x] += val;
x += lowbit(x);
}
}
// 注意判断质数的写法
bool isPrime(int x){
if(x <= 1)
return false;
if(x == 2)
return true;
int tmp = sqrt(x);
for(int i = 2 ; i <= tmp ; i++)
if(x%i == 0)
return false;
return true;
}
void init(){
int x = 0;
if(isPrime(val))
x = 1;
memset(treeNum , 0 , sizeof(treeNum));
for(int i = 1 ; i <= n ; i++){
num[i] = val;
add(i , x);
}
}
void solve(int mark , int x , int y){
if(mark == 1){
int ans = getSum(y);
ans -= getSum(x-1);
printf("%d\n" , ans);
}
else{
int tmp = num[x];
num[x] += y;
if(isPrime(num[x])){
if(!isPrime(tmp))
add(x , 1);
}
else{
if(isPrime(tmp))
add(x , -1);
}
}
}
int main(){
int cas = 1;
int m , mark;
int x , y;
while(scanf("%d%d%d" , &n , &m , &val) &&n+m+val){
init();
printf("CASE #%d:\n" , cas++);
while(m--){
scanf("%d%d%d" , &mark , &x , &y);
solve(mark , x , y);
}
puts("");
}
return 0;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。
原文：http://blog.csdn.net/acm_10000h/article/details/48093233