HIT 1867 经理的烦恼

题目链接:http://acm.hit.edu.cn/hoj/problem/view?id=1867

每次更新时判断是否素数,如果从非素数变成素数就Update(x, 1),如果从素数变成非素数就Update(x, -1)。

 1 /*HIT 1867
 2 经理的烦恼 
 3 */
 4 #include<cstdio>
 5 #include<cstring>
 6 const int N=1009;
 7 
 8 int a[N],c[N],n,m,C;
 9 int prime(int num)
10 {
11     int i;
12     if(num<=1)return 0;
13     for(i=2; i*i<=num; i++)
14     {
15         if(num%i==0)
16             return 0;
17     }
18     return 1;
19 }
20 int lowbit(int x)
21 {
22     return x & (-x);
23 }
24 
25 void update(int i,int m)
26 {
27     while(i<=C)
28     {
29         c[i] += m;
30         i += lowbit(i);
31     }
32 }
33 int Sum(int num)
34 {
35     int s =0;
36     while(num>0)
37     {
38         s += c[num];
39         num -= lowbit(num);
40     }
41     return s;
42 }
43 int main()
44 {
45     //freopen("1867.txt","r",stdin);
46     int i,j,k,x,y,t,time=0;
47     while(scanf("%d %d %d",&C,&n,&m)!=EOF)
48     {
49         if(C==0&&n==0&&m==0) break;
50         t = prime(m);
51         memset(c,0,sizeof(c));
52         for(i=1; i<=C; i++)
53         {
54             if(t!=0)
55             {
56                 update(i,1);
57             }
58             a[i]=m;
59         }
60         printf("CASE #%d:\n",++time);
61         for(i=0; i<n; i++)
62         {
63             scanf("%d %d %d",&k,&x,&y);
64             if(k==0)
65             {
66                 int tmp = a[x];
67                 a[x]+=y;
68                 if(prime(a[x]))
69                 {
70                     if(!prime(tmp))
71                         update(x,1);
72                 }
73                 else
74                 {
75                     if(prime(tmp))
76                         update(x,-1);
77                 }
78 
79             }
80             else
81                 printf("%d\n",Sum(y)-Sum(x-1));
82         }
83         printf("\n");
84 
85     }
86     return 0;
87 }

 

 

更多相关文章
  • 随着越来越多的企业使用SAP,如何让让外地辦事处以及供应商使用SAP已经不再IT经理的烦恼?作为应用虚拟化的王者,Citrix XenApp当之无愧. 首先我们需要了解SAP的基本信息, 1. SAP的配置文件存储以
  • 


    		    SVN集成Checkstyle實現代碼自動檢查
    日常做开发管理,开发经理或者项目经理最烦恼的是怎么控制团队成员的代码质量,团队成员背景不同.经验不同,开发出来的产品也参差不齐,如果只靠代码走查,工作量太大,效果也不好,如果靠事后检查,或者出问题了再来追责,效果也不好.因此需要考虑一种事前自动化检查的方式,这样就能简化开发经理或项目经理的工作,让管
  • [HIS] HIT行业常用名词及缩写定义 1.   EHR 居民个人电子健康记录 2.   MPI 居民个人主索引 3.   HIS 医院管理信息系统 4.   CIS 医院临床信息系统 5.   PRM 患者关系管
  • 


    		    3不原則:如何在HIT行業找到合適的“東家”
    找工作.招人才其实和找对象差不多,没有最好,只有是否合适.公司找到合适的人才,人才选择合适
  • The library cache (a component of the shared pool) stores the executable (parsed or compiled) form of recent
  • hdu 1867 A + B for you again
    题目连接 http://acm.hdu.edu.cn/showproblem.php?pi
  • http://space.itpub.net/12361284/viewspace-154924 在系统运行过程中,如果我们发现Cache hit rate过小,或者我们通过观察statspack中的Instance Efficiency Percentages这部分呢,我们会发现Buffer Hi ...
  • Despite some hype and a few regional exceptions, the construction of office towers and suburban office parks has not made a significant resurgence in
一周排行
  • iOS開發筆記Masonry介紹與使用實踐:快速上手Autolayout
    前言 原文地址:http://www.cocoachina.com/ios/2014121 ...
  • 任意軸算法 ( Arbitrary Axis Algorithm )
    已知三维空间中任意单位向量,求以该向量为Z轴的local正交坐标系: 如上图,每个模型都有
  • 


    		    J2EE搭建之三 J2EE目錄結構
    本文出自 "JAVAWeb开发" 博客,请务必保留此出处http:// ...
  • 调整问题间, 巩固下知识,发现网上的写的很乱,自己写个简短易懂的; 跑下程序一切明了; /** * * @author wyd * @description * 类描述: * return break continu ...
  • 异常信息:Unexpected Exception caught setting 'outHeight' on 'class com.srpm.core.project.seismicFortification.ac
  • 第五部分 IP源保护(IP Source Guard) IPSG提供检测机制来确保单个接口所接收到的数据包能够被各个接口所接收.如果检查成功通过,那么就将许可数据包:否则就会发生违背策略的活动.IPSG不仅能够确保第
  • DateDiff函数返回 Variant (Long) 的值,表示两个指定日期间的时间间隔数目. 语法 DateDiff(interval, date1, date2[, firstdayofweek[, first
  • 1.[原创]Android 系统稳定性 - OOM(一) 2.[原创]Android 系统稳定性 - OOM(二)     3.Android内存泄露分析(MemoryAnalyzer工具)
  • 以前,一直使用的是officescan7.0的版本,用了好久. 后来找过8.0的序列号,一直没有找到过,也就作罷了升级的心思. 但是,昨天,很意外的,突然发现了officescan10版的序列号,只不过,据说是针对繁
  • 在工作中用到的例子: select * FROM [CSGDC.DataETLDB].[dbo].[StrategiesList] where strategy_name like '%基建系统%' and SUBS ...