打卡信奥刷题（3268）用C++实现信奥题 P8842 [传智杯 #4 初赛] 小卡与质数 2

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=1<<21;boolf[N+10];intp[N+10],k;intcnt[30];voidqwq(){for(inti=2;i<=N;i++){//线性筛if(f[i]==0){p[++k]=i;}for(intj=1;j<=k&&i*p[j]<=N;j++){f[i*p[j]]=1;if(i%p[j]==0){break;}}}for(inti=1;i<=k;i++){for(intj=22;j>=0;j--){if(p[i]&(1<<j)){cnt[j]++;//计算当质数为j位时，一共的个数break;}}}}intmain(){qwq();//预处理intt;cin>>t;while(t--){intn,c=0;cin>>n;for(inti=22;i>=0;i--){if(n&(1<<i)){c+=cnt[i];//最后计算数量}}cout<<c<<endl;}return0;}

后续

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