HDU 4548 美素数 在线打表加数状数组

时间：2023-03-10 07:31:46
HDU 4548 美素数 在线打表加数状数组

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4548

解题报告：一开始本想先打个素数表，然后每次输入L 跟R 的时候都进行暴力判断，但这题测试数据太多，有1W ，这样就达到10^10级别了，很明显不能过，但是，我后来一想，数状数组不就是用来解决区间问题的吗，顿时焕然大吾。我的做法就是先打个1到1000000的素数表，然后暴力判断从1到1000000每个数是不是美素数，同时把结果存到数状数组里面去。这样就可以实现存完了就可以实现快速查找了。

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<cmath>

 const int maxn = ;

 int prim[maxn+],tree[maxn+];

 void dabiao()

 {

     memset(prim,,sizeof(prim));

     prim[] = ;

     for(int i = ;i <= maxn;i += )

     prim[i] = ;

     int M = sqrt(maxn);

     for(int i = ;i <= M;++i)

     if(prim[i] == )

     for(int j = i*i;j<=maxn;j+=i)

     prim[j] = ;

 }

 int judge(int n)

 {

     int sum = ;

     while(n)

     {

         sum += n%;

         n /= ;

     }

     return sum;

 }

 void add(int n)

 {

     if(n > maxn)

     return ;

     for(int i = n;i <= maxn;i += (i&-i))

     tree[i]++;

 }

 void dabiao2()

 {

     memset(tree,,sizeof(tree));

     for(int i = ;i <= maxn;++i)

     if(!prim[i] && !prim[judge(i)])

     add(i);

 }

 int sum(int L,int R)

 {

     int tot1 = ,tot2 = ;

     for(int i = L-;i >= ; i -= (i&-i))

     tot1 += tree[i];

     for(int i = R;i >= ;i -= (i&-i))

     tot2 += tree[i];

     return tot2 - tot1;

 }

 int main()

 {

     dabiao();

     dabiao2();

     int T,L,R,l = ;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d %d",&L,&R);

         printf("Case #%d: %d\n",l++,sum(L,R));

     }

     return ;

 }