P8842 [传智杯 #4 初赛] 小卡与质数 2

题目背景

小卡迷上了质数！

题目描述

小卡最近迷上了质数，所以他想把任何一个数都转化为质数！

小卡有TTT次询问，每次给你一个数字xxx，问有多少个比xxx小的非负整数yyy，使得x⊕yx\oplus yx⊕y是质数，其中⊕\oplus⊕表示按位异或。

输入格式

第一行一个正整数T(1≤T≤105)T(1\le T\le10^5)T(1≤T≤105)，表示有TTT组询问。

接下来TTT行，每行一个正整数x(1≤x≤106)x(1\le x\le 10^6)x(1≤x≤106)。

输出格式

对于每组询问，输出一行一个整数，表示答案。

输入输出样例 #1

输入 #1

9 5 6 7 8 9 10 100 1000 10000

输出 #1

2 4 4 2 2 4 22 163 1132

C++实现

#include<bits/stdc++.h>usingnamespacestd;constintN=1e7+10;intprime[N],sum[N];intmain(){intn;cin>>n;prime[0]=prime[1]=1;for(inti=2;i<=N-10;i++){if(prime[i])continue;for(intj=2;i*j<=N-10;j++)prime[i*j]=1;}for(inti=1;i<=N-10;i++)sum[i]=sum[i-1]+(!prime[i]);for(inti=1;i<=n;i++){intx,ans=0;cin>>x;for(intj=0;j<=30;j++)if(x&(1<<j))ans+=sum[(1<<(j+1))-1]-sum[(1<<j)-1];cout<<ans<<'\n';}return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容