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

Adolfo_North · 2023-01-27 13:34:09 · 题解

传送门

变态数学题（主考位运算与素数筛）。

读完题看起来有点难做，因为质数的出现是根本没有可以使用的规律。暴力的话也很好想，枚举 y。但是肯定会超时。我们也可以换个方向枚举。对，筛出素数，再返过去判断有多少个素数符合条件，但任然会超时。

再思考一下，x 异或上什么样的数才能使结果小于 x？

注意下面的步骤需要草稿纸推演，不然会有点难理解。

我们设符合条件的素数为 k ，我们设 k 的二进制中最高位是第 M 位，不难发现，只有在 x 的第 M 位上也是 1 的时候，k 异或 x 的结果小于 x（这一步若实在想不通的可以拉到文末，查看证明过程）。

随即。我们用素数筛，并统计范围内所有素数的最高位是哪一位，对于每个询问把 x 每位拆开，若发现某一位是 1，则加上桶里已经计算好的，二进制数该位为 1 的素数个数。

代码奉上：

#include<iostream>
using namespace std;
int T,n,m,ans;
int zhi[2000010],cnt[26];
bool f[2000010];
void IAKchuanzhibei(){
    //素数筛 （欧拉筛法） 
    for(int i=2;i<=2000000;i++){
        if(!f[i])zhi[++m]=i;
        for(int j=1;j<=m&&i*zhi[j]<=2000000;j++){
            f[i*zhi[j]]=1;
            if(!(i%(zhi[j])))break;
        }
    }
    //开桶记录 
    for(int i=1;i<=m;i++)
        for(int j=25;j>=1;j--)//由于1000000内最大的质数为999983,转成二进制为1111 0100 0010 0010 1111，共24位，为保险起见，这里从25开始计算 
            if(zhi[i]&(1<<(j-1))){
                cnt[j]++;//计算当质数为j位时，一共的个数 
                break;
            }
}
int main()
{
    //预处理 
    IAKchuanzhibei();

    cin>>T;
    while(T--)
    {
        cin>>n;
        ans=0;
        for(int i=25;i>=1;i--) if(n&(1<<(i-1))) ans+=cnt[i];//加上所有符合条件的素数 
        cout<<ans<<endl;
    }
    return 0;
}

证明过程：

观点一：那么 k 异或 x 的结果从 M+1 位开始与 x 的 M+1 位开始的部分相同。因为 k 的 M+1 位以上的部分均为 0，因为 1 异或 0 的结果为 1，0 异或 0 的结果为 0，所以保持不变。

观点二：那么重点来到 M 位，由于 k 的 M 位一定为 1，那么如果 x 的 M 位也为 1，异或一下结果为 0，即小于原来 x 的 M 位，那么异或的结果一定小于 x。若 x 的 M 位为 0，则反之。

我们设 x=13，并拿质数 3 和 5 举例。