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输入 #19 5 6 7 8 9 10 100 1000 10000输出 #12 4 4 2 2 4 22 163 1132C实现#includebits/stdc.husingnamespacestd;constintN1e710;intprime[N],sum[N];intmain(){intn;cinn;prime[0]prime[1]1;for(inti2;iN-10;i){if(prime[i])continue;for(intj2;i*jN-10;j)prime[i*j]1;}for(inti1;iN-10;i)sum[i]sum[i-1](!prime[i]);for(inti1;in;i){intx,ans0;cinx;for(intj0;j30;j)if(x(1j))anssum[(1(j1))-1]-sum[(1j)-1];coutans\n;}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容