自动搬运

查看原文

来自洛谷，原作者为

	fdszlzl **

搬运于2025-08-24 22:43:00，当前版本为作者最后更新于2022-11-12 03:55:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

题意：给定 $T$ 个 $x$ ，求有多少个小于 $x$ 的非负整数与 $x$ 异或的结果为质数。

$x⊕y=p (y < x)$

要枚举 $y$ ，时间复杂度 $O(Tx)$

$x⊕y=p \to x⊕p=y(y < x)$

要枚举 $p$ ，时间复杂度 $O(Tz)$ 。百万内的质数有$z$个（几万）。

因为 $y<x$，异或后值变小。什么情况异或后值会变小？

设 $x=(100100)_2$

要想异或后值变小，$1$ 必须变成 $0$

$1⊕1=0$

• 第一个$1$

$100100⊕ 1***** = 0***** <100100$

换言之，$100100⊕(100000 \sim 111111)$ 的值都小于 $100100$

即，$x⊕(2^5 \sim 2^6-1)$ 的值小于 $x$

现在我们只要算出 $(2^5 \sim 2^6-1)$ 有几个质数即可，前缀和。

• 第二个 $1$

$100100 ⊕ 0001** = 1000** <100100$

换言之， $100100⊕(000100 \sim 000111)$ 的值都小于 $100100$

即， $x⊕(2^2 \sim 2^3-1)$ 的值小于 $x$

现在我们只要算出 $(2^2 \sim 2^3-1)$ 有几个质数即可。

总之，若 $x$ 的第 $i$ 位为 $1$，算出 $2^i \sim 2^{i+1}-1$ 有多少个质数累加即可。

注意，$x⊕p=y(y < x)$， $p$ 有可能超过 $x$ 。

#include <bits/stdc++.h>
using namespace std;

const int N=1e7+10;
int prime[N],sum[N];

int main() {
	int n;
	cin>>n;
	prime[0]=prime[1]=1;
	for(int i=2;i<=N-10;i++)
	{
		if(prime[i]) continue;
		for(int j=2;i*j<=N-10;j++) prime[i*j]=1;
	}
	for(int i=1;i<=N-10;i++) sum[i]=sum[i-1]+(!prime[i]); 
	for(int i=1;i<=n;i++)
	{
		int x,ans=0;
		cin>>x;
		for(int j=0;j<=30;j++)
			if(x&(1<<j)) 
				ans+=sum[(1<<(j+1))-1]-sum[(1<<j)-1];
		cout<<ans<<'\n';
	}
	return 0;
}