思想区-我的第一印象

这题是模板题，而且要我预处理质数，那肯定要线性筛，加个异或还原，因为异或同一个数两次，就是原来的数。但是我的代码在1e6的情况下会wa,搞不懂啊？！？！？！

后来是peter学长说:
如果某一个数的二进制是xxxx..xx有n位x，那么这个数和任意一位数想亦或能够得到的最大的数是111…111，n位1，n位1就是2的n+1次方减一，就是说小于2的n+1次方减一的任意素数都有可能被取到。这道题x的最大范围是到一百万，一百万，也就是有20位，所以范围最大情况就是二十位全是1，2的二十次方是一百万,2的二十一次方就是两百万

2e6的情况下直接爆

思想区-peter学长的讲解

就从高位到低位按位分析。

如果x的某一位是1，得到的素数的这一位也是1，那么y的这一位一定是0。
这种情况下，y是一定小于x的，符合这种情况的素数能被算入答案。

如果x的某一位是1，得到的素数的这一位是0，那么y的这一位一定是1。
这种情况下，x和y的大小不确定，所以满足这个条件的素数不能被算入答案。

如果x的某一位是0，得到的素数的这一位是1，那么y的这一位一定是1。
这种情况下，x一定小于y，所以满足这个条件的素数不能被算入答案。

如果x的某一位是0，得到的素数的这一位是0，那么y的这一位一定是0。
这种情况下，x和y的大小不确定，所以满足这个条件的素数不能被算入答案。

所以预处理素数表的时候，要处理出以每一位为最高位的素数的个数。然后从高位到低位枚举，如果x的某一位为1，就把以这一位为最高位的素数个数加上，就能得到答案。

代码区-peter学长的代码

#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector> 

using namespace std;

const int N = 2000010;

int t;
int primes[N], cnt;
int num[32];
bool st[N];

int lowbit(int x) 
{
    return x & -x;
}

//线性筛
void get_primes(int n)
{
    st[0] = st[1] = true;//0和1不符合条件
    for(int i = 2;i <= n;i ++)
    {
        if(!st[i]) primes[cnt ++] = i;

        for(int j = 0;primes[j] <= n / i;j ++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}


int main()
{
    get_primes(N - 1);//找到N-1之前的素数


    //peter学长debug用的
    // for(int i = 0;i <= 20;i ++) cout << (int) pow(2, i) << endl;

    cin >> t;//输入t


    //在筛出来的素数中得到的数
    for(int i = 0;i < cnt;i ++) 
    {
        int t = primes[i];
        for(int j = 31;j >= 0;j --) 
            if(t >> j & 1)
            {
                num[j] ++;
                break;
            }
    }

    //累加每一个1为最大值的素数个数
    while(t --)
    {
        int n;
        cin >> n;

        int res = 0;
        for(int i = 0;i < 32;i ++) 
            if(n >> i & 1) 
                res += num[i];

        cout << res << endl;
    }

    return 0;
}

代码区-我的代码，会爆

#include<iostream>
#include<algorithm>

using namespace std;

int T;//询问数字 


const int N= 1000110;

int primes[N],cnt;//存数组和计数器 
bool st[N];

void get_primes(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++)
        {
            st[primes[j]*i]=true;
            if(i%primes[j]==0)break;
        }
    }
}

int main()
{
    get_primes(N);
    scanf("%d",&T);
    while(T--)
    {
        int x=0,res=0;

        scanf("%d",&x);


            for(int i=0;i<cnt;i++)
            {
                int temp=primes[i]^x;
                if(temp>=0&&temp<x)res++;
            }
            printf("%d\n",res);



    }


    return 0;
}