Codeforces 385C 线性筛素数

题意：给定一个数组，求[l,r] 区间，区间里的素数，数组中，能被这个素数整除的个数，再求和。

分析：区间很大，10^9了，找去区间内的素数是不可能的，但是，数组的数很小，而且要能整除区间内的素数，所以，这些很大的素数是没用的，筛出10^7以内的素数就ok了。

怎么算个数呢？

质因数分解，hash一下，再二分区间，应该是很麻烦了，但是网上还有麻烦的，还用到了线段树维护。

简单方式是：

将数组hash，在筛素数的时候，检测hash值，是否有这些数，有的话，记录到这个素数中，也就是说，这个数组中，能被这个素数整除的有s个，然后对s求一个前缀和，问题就转换为一个区间和。

#include <bits/stdc++.h>

using namespace std;

//10^7以内的素数

const int maxn = +;

int vis[maxn],g[maxn],s[maxn];

int m;

int main(int argc, char const *argv[])

{

    memset(vis,,sizeof(vis));

    memset(g,,sizeof(g));

    memset(vis,,sizeof(vis));

    int n;

    scanf("%d",&n);

    for(int i=;i<n;i++) {

        int x;

        scanf("%d",&x);

        g[x]++;

    }

    for(int i=;i<maxn;i++) {

        if(vis[i]) continue;

        for(int j=i;j<maxn;j+=i) {

            if(g[j])

                s[i] +=g[j];

            vis[j] = ;

        }

    }

    for(int i=;i<maxn;i++)

        s[i] +=s[i-];

    int a,b;

    scanf("%d",&m);

    for(int i=;i<m;i++) {

        scanf("%d%d",&a,&b);

        if(a>=maxn) a = maxn-;

        if(b>=maxn) b = maxn-;

        printf("%d\n",s[b]-s[a-]);

    }

    return ;

}

巴特西

Codeforces 385C 线性筛素数

最新文章

热门文章