E题题解

题意

有两个要求： 1.求某个区间的质数的个数； 2.先求出由该区间内质数组成的数组，然后求该数组有多少个子区间使得子区间内的数AND和为0；

分析

因为题目给的时间为2秒(对于c++来说),所以可以预先筛选出1~1e8内的质数，这样就可以求出某段区间的质数数组以及质数个数了；其次求子区间个数，我们发现质数除了2以外都是奇数，也就意味着它们的最低位都是1，显然如果质数数组没有2的话，其他质数的AND和不可能为0；对于有2的情况，可以直接枚举质数数组，从前往后求AND和，如果在在下标i的AND和为0，那么i后面的AND和一定为0，因为0AND任何数都为0，所以子区间个数就为k-i(k为质数数组的长度)。

c++代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<iomanip>
#include<unordered_set>
#include<queue>
#include<cmath>
#include<stack>
#define  FI(x) fixed<<setprecision(x)
using namespace std;
const int N = 100000010,M=10000010;
int prim[N];
bool st[N];
int cot;
void init()
{
    for(int i=2;i<=N;i++)
    {
        if(!st[i])
          prim[cot++]=i;
        for(int j=0;prim[j]<=N/i;j++)
        {
            st[prim[j]*i]=true;
            if(i%prim[j]==0)
              break;
        }
    }
}
int main()
{
    init();
    int t;
    cin>>t;
    while(t--)
    {
        int x,y;
        cin>>x>>y;
       // vector<int> A;
        int b[N];
        int k=0;
        for(int i=0;i<cot;i++)
        {
            if(prim[i]>=x&&prim[i]<=y)
            {
                //A.push_back(prim[i]);
                b[k++]=prim[i];
            }
            else if(prim[i]>y)
                break;
        }
        cout<<k<<" ";
        if(k==0)
        {
            cout<<0<<'\n';
            continue;
        }
        if(b[0]!=2)
        {
            cout<<0<<'\n';
            continue;
        }
        int m=0;
        int u=b[0];
        for(int i=1;i<k;i++)
        {
            u&=b[i];
            if(u==0)
            {
                m=k-i;
                break;
            }
        }
        cout<<m<<'\n';
    }
    return 0;
}