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=1000009;

 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:
",++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
",Sum(y)-Sum(x-1));

82         }

83         printf("
");

84 

85     }

86     return 0;

87 }