线性筛裸题。
首先要记住一个结论：
对于一个数\(n\)，不大于他的素数不超过\(\sqrt{n}\)
然后就直接算出\([2,min(k,\sqrt{R})]\)范围内的素数，将他们在\([L,R]\)范围内的倍数标记，最后没有标记的就是“类素数”。
直接异或没被标记的数即可。
Code
#include<bits/stdc++.h>
using namespace std;
namespace STD
{
#define rr register
typedef long long ll;
const int N=1e7+4;
int cnt;
ll l,r,k;
ll ans;
ll read()
{
rr ll x_read=0,y_read=1;
rr char c_read=getchar();
while(c_read<'0'||c_read>'9')
{
if(c_read=='-') y_read=-1;
c_read=getchar();
}
while(c_read<='9'&&c_read>='0')
{
x_read=(x_read<<3)+(x_read<<1)+(c_read^48);
c_read=getchar();
}
return x_read*y_read;
}
ll prime[N];
bool is_not_prime[N];
bool no[N];
void pre()
{
ll up=sqrt(r)+1;
for(int i=2;i<=min(k,up);i++)
{
if(!is_not_prime[i]) prime[++cnt]=i;
for(int j=1;j<=cnt&&prime[j]*i<=min(k,up);j++)
{
is_not_prime[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
};
using namespace STD;
int main()
{
l=read(),r=read(),k=read();
pre();
for(int i=1;i<=cnt;i++)
for(ll j=max(2ll,l/prime[i]);j*prime[i]<=r;j++)
{
ll temp=j*prime[i]-l;
if(temp>=0)
no[temp]=1;
}
for(int i=0;i<=(r-l);i++)
if(!no[i])
ans^=(l+i);
printf("%lld\n",ans);
}
时间复杂度\(O((r-l)*log(logR))\)
标记倍数的这一步好像叫“埃氏筛法”，复杂度主要在这里，就是\(O((r-l)*log(logR))\)。
严格的复杂度是\(O(n+(r-l)*log(logR))\)。\(n\)是线性筛。