【位运算+数论】P8842 [传智杯 #4 初赛] 小卡与质数2

fdszlzl · 2022-11-12 03:55:43 · 题解

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

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

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

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

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

设 x=(100100)_2

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

• 第一个1

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

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

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

• 第二个 1

换言之， 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;
}