题目描述
思路
题目给定我们 \(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;
}
标签:落谷,int,质数,++,--,&&,primes
From: https://www.cnblogs.com/ALaterStart/p/16913036.html