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