题解 P6067 【[RC-02] yltx 数对】

· · 题解

Update on 2020.5.11

bitset 优化筛法。

首先 10^7 组询问，肯定要预处理出范围内的所有素数然后 O(1) 判断。

线性筛会爆空间（似乎也能过？），只能用埃氏筛。

先筛掉 2,3 的倍数，然后在 6 个里面只用筛 2 个：i(6i+1)，i(6i+5)。

用 bitset 压一下位就行了。注意不需要筛偶数，可大大减少时间和空间。

std：

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
int k=1,s[10005],prime[10005];
bitset<50110005>vst;
inline bool Prime(register int n){
    return n<2?0:(n==2?1:(n%2&&!vst[n>>1]));
}
int main() {
//  freopen("5.in","r",stdin);
//  freopen("5.out","w",stdout);
    for(int i=9; i<=100030000; i+=6)vst[i>>1]=1;
    for(int i=15; i<=100030000; i+=10)vst[i>>1]=1;
    for(register int i=7; i<=20000; i+=2){
        if(vst[i>>1])continue;
        for(register int j=i*(i/6*6+1); j<=100030000; j+=i*6){
            vst[j>>1]=1;
            vst[(j>>1)+(i<<1)]=1;
        }
    }
    int T,x0,y0,s=0;
    scanf("%d%d%d",&T,&x0,&y0);
    while(T--){
        x0=((7*x0+13)^(x0/13-7));
        y0=((7*y0+13)^(y0/13-7));
        int x=(x0%10000+10000)%10000+1,y=(y0%10000+10000)%10000+1;
        if(Prime(x)&&Prime(y)&&Prime(x*y-3*(x-y)))s++;
    }
    cout<<s;
    return 0;
}