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
一周排行
  • 


    		    cacti下交換機端口圖像中Inbound與Outbound的理解
    具体图像如下: 端口21下连接的终端IP为10.240.240.69. 机器从外部下载文件 ...
  •      Windows提供了4种不同的方法来接收I/O请求已经完成的通知:触发设备内核对象.触发事件内核对象.可提醒I/O和I/O完成端口.      Windows的异步I/O     当线程向设备发起一个I/O
  • LocalDB (SqlLocalDB)LocalDB 是 Express 的一种轻型版本,该版本具备所有可编程性功能,但在用户模式下运行,并且具有快速的零配置安装和必备组件要求较少的特点.如果您需要通过简单方式从代
  • 轉 CSS3實現10種Loading效果
    昨晚用CSS3实现了几种常见的Loading效果,虽然很简单,但还是分享一下,顺便也当是做 ...
  • Adaptive Server Enterprise 15.0 Driver={Adaptive Server Enterprise};app=myAppName;server=myServerAddress;por ...
  • CSS hack:针对IE6,IE7,firefox显示不同效果 做网站时经常会用到,衡量一个DIV+CSS架构师的水平时,这个也很重要. 区别不同浏览器的CSS hack写法: 区别IE6与FF:         ...
  • 往上看了在.bash_profile中配置 然后 source  的方法, 试过了, 只是当前的终端有效,当电脑重启或者关闭终端就失效了,只好看看 mac 的 profile 代码   # System-wide . ...
  • 一.Bitcoin-qt客户端加密后 如需要导出某一地址对应的私钥,需要先调用 walletpassphrase 密码 解锁持续时间(秒), 如:walletpassphrase h123456789*/* 120,
  • 如果要插入几十甚至几百张图片,并且要求每张图片插入到每张幻灯片 页面上(即有几张照片就要有几张幻灯片)你会怎么做? 按照常用的方法点击"插入→图片→来自文件"菜单命令,然后一个一 个选择需要的图片 ...
  • where cast(soh.orderdate as date)=cast(dateadd(day,-1,getdate()) as date) 这一代码在sql 2005 不适用,使用convert 函数将容器改