LA 3998 Prime—k tuple

题意

给定 $a,b(1 < a < b < 2000000000)$
再给定 $k,s$ 求区间$[a,b]$中有多少个$k$元组
$k$元组满足：共有$k$个相邻的素数，且第一个和最后一个素数的差值等于$s$

分析

先用筛法预处理出$\sqrt{2000000000}$内的素数,
然后对于区间 $[a,b]$ ，再用这些素数去暴力筛出其他的素数。
最后扫描一遍筛出的素数，确定答案。

这里，按照道理来说。。$2000000000$以内的素数有将近$1$亿个，但是开那么大的空间会$RE$，不知为何，最后开到的是 $1000w$ 的数组

另外，这里也可以是，先筛出$\sqrt{2000000000}$内的素数,其他的素数用米勒拉宾来判断。不过貌似并不是很快。。。

!!!!! 另外，，这里切记不要去使用$mul()$，，，我擦，，这样会极大程度得减慢$miller~-rabin$的速度，。

!!!!! 再另外，，题目没有给内存限制，，这也是一个很蛋疼的事

代码1

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define clr( a, b ) memset( a, b, sizeof(a) )
#define SIZE 5000000
int t, a, b, k, s, tot;
int vis[ SIZE + 10 ], pri[ SIZE + 10 ], p[ 11000000 ];
void init(){
    vis[0] = vis[1] = 1;
    int m = sqrt( SIZE + 0.5 );
    for( int i = 2; i <= m; ++i )   if( !vis[i] )
        for( int j = i * i; j <= SIZE; j += i ) vis[j] = 1;
    tot = 0;
    for( int i = 2; i <= SIZE; ++i ) if( !vis[i] )
        pri[ tot++ ] = i;
}
const int S = 8;
LL fast_mod( LL a, LL b, LL M ){
    LL res = 1;
    while( b ){
        if( b & 1 ) res = res * a % M;
        a = a * a % M;
        b >>= 1;
    }
    return res;
}
bool miller_rabin( LL n ){
    if( n < 2 )  return false;
    if( n == 2 ) return true;
    if( !( n & 1 ) ) return false;
    int t = 0;
    LL cur, pre, u = n - 1;
    while( !( u & 1 ) ){
        t++;
        u >>= 1;
    }
    for( int i = 0; i < S; ++i ){
        LL a = rand() % ( n - 2 ) + 2;
        cur = fast_mod( a, u, n );
        pre = cur;
        for( int j = 0; j < t; ++j ){
            cur = pre * pre % n;
            if( cur == 1 && pre != 1 && pre != n - 1 )
                return false;
            pre = cur;
        }
        if( cur != 1 ) return false;
    }
    return true;
}
bool check( int x ){
    if( x <= SIZE ){
        return vis[x] == 0;
    }
    if( miller_rabin( 1LL * x ) ){
        return true;
    }else{
        return false;
    }   
}
int main(){
    init();
    scanf( "%d", &t );
    srand( time( NULL ) );
    while( t-- ){
        scanf( "%d %d %d %d", &a, &b, &k, &s );
        int cnt = 0;
        for( int i = a; i <= b; ++i ){
            if( check(i) ){
                p[ cnt++ ] = i;
            }
        }
        int ans = 0;
        for( int i = 0; i < cnt - k + 1; ++i ){
            if( p[i+k-1] - p[i] == s ){
                ans++;
            }
        }
        printf( "%d\n", ans );
    }
    return 0;
}

代码2

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define clr( a, b ) memset( a, b, sizeof(a) )
#define SIZE 5000000
int t, a, b, k, s, tot;
int vis[ SIZE + 10 ], pri[ SIZE + 10 ], p[ 11000000 ];
void init(){
    vis[0] = vis[1] = 1;
    int m = sqrt( SIZE + 0.5 );
    for( int i = 2; i <= m; ++i )   if( !vis[i] )
        for( int j = i * i; j <= SIZE; j += i ) vis[j] = 1;
    tot = 0;
    for( int i = 2; i <= SIZE; ++i ) if( !vis[i] )
        pri[ tot++ ] = i;
}
bool check( int x ){
    if( x <= SIZE ){
        return vis[x] == 0;
    }else{
        for( int i = 0; i < tot && pri[i] * pri[i] <= x; ++i ){
            if( x % pri[i] == 0 ){
                return false;
            }
        }
    }   
    return true;
}
int main(){
    init();
    scanf( "%d", &t );
    while( t-- ){
        scanf( "%d %d %d %d", &a, &b, &k, &s );
        int cnt = 0;
        for( int i = a; i <= b; ++i ){
            if( check(i) ){
                p[ cnt++ ] = i;
            }
        }
        int ans = 0;
        for( int i = 0; i < cnt - k + 1; ++i ){
            if( p[i+k-1] - p[i] == s ){
                ans++;
            }
        }
        printf( "%d\n", ans );
    }
    return 0;
}