落谷 R94951828 -- 位运算&&质数&&思维

题目描述

传智杯

思路

题目给定我们 \(x\)，让我们找到小于 \(x\) 的 \(y\) 使得 \(x^y\) 为质数。
用 \(p\) 来表示质数。
$x⊕y=p → x⊕p=y, ∵y<x，∴x⊕p<x $
那么题目就转化为了求 \(x⊕p < x\) 的质数 \(p\) 的个数。
我们可以先线性筛得到所有的质数，对于每个质数与处理如下：
如果 \(p\) 的二进制中最高位是第 \(h\) 位，考虑 \(x\) 的二进制中的每一位，当且仅当 \(x\) 的第 \(x\) 位上也是 \(1\) 的时候，\(k\) 异或 \(x\) 的结果小于 \(x\)。（分类讨论)
所以我们预处理所有质数它们的最高位是哪一位，并开个桶记录一下，对于每个询问把 \(x\) 拆位求一下就好了。

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2000010, M = 100010;
// 这里n为什么开成两倍
// 例如 n=100 = 4
// 但是 n^11 = 111 = 7
// 懂了吧！虽然11比n小，但是他和n构成的质数可能比n大
// 最多大2倍然后减1

int T;
int primes[N], idx;
bool st[N];
int bucket[32];

void get_primes() {
    for(int i = 2; i < N; i ++ ) {
        if(!st[i]) primes[idx ++ ] = i;
        for(int j = 0; primes[j] < N / i; j ++ ) {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0)  break;
        }
    }
    // cout << "idx: " << idx << endl;
    for(int i = 0; i < idx; i ++ ) {
        for(int j = 30; j >= 0; j -- ) {
            if(primes[i] >> j & 1)  { 
                bucket[j] ++;
                break;  // 找到最高位就break掉！
            }
        }
    }
}

int main()
{
    get_primes();
    cin >> T;
    while( T -- ) {
        int x;  cin >> x;
        int ans = 0;
        for(int i = 30; i >= 0; i -- ) {
            if(x >> i & 1)  ans += bucket[i];
        }
        cout << ans << endl;
    }
    
    return 0;
}