题意：首先给你N个数。然后有M次询问，每次询问给出一段区间，首先找出这段区间内的所有素数，然后计算对于这段区间内第 i 的素数Pi，这N个数中有多少个数能被Pi整除，设有Si个数能被Pi整除，然后输出Si的和。

思路：因为这个N个数的范围为 [ 2 , 1000W]，所以只需找出这一段区间的素数即可，貌似67W个左右。

memset(mark,0,sizeof(mark));

    for(i = 2;i <= 10000000; ++i)
    {
        if(mark[i] == 0)
        {
            num[top++] = i;
            for(j = i;j <= 10000000; j += i)
            {
                mark[j] = 1;
            }
        }
    }

然后是对于这N个数的预处理。可以先用Hash的思路处理一下，然后用类似于素数筛的方法统计一下Si。

memset(mark,0,sizeof(mark));

    int n;

    scanf("%d",&n);

    for(i = 0;i < n; ++i)
    {
        scanf("%d",&j);
        mark[j]++;
    }

    for(i = 0;i < top; ++i)
    {
        for(ans[i] = 0,j = num[i];j <= 10000000; j += num[i])
        {
            if(mark[j] > 0)
                ans[i] += mark[j];
        }
    }

接下来就是二分查找给出的区间内的素数 和 最基本的线段树求区间和了，不再赘述。

其实这个题让我感到诧异的地方是，他竟然能开出 这么大的数组。。。

下面是完整的代码。

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cmath>
#include <algorithm>

#define LL long long
#define PI (acos(-1.0))
#define EPS (1e-10)

using namespace std;

int mark[10000001];

int num[700000];
int ans[700000];

LL st[2800000];

void Init_St(int site,int l,int r)
{
    if(l == r)
    {
        st[site] = ans[l];
        return ;
    }

    int mid = (l+r)>>1;

    Init_St(site<<1,l,mid);
    Init_St(site<<1|1,mid+1,r);

    st[site] = st[site<<1] + st[site<<1|1];
}

int Position_R(LL m,int n)
{
    int s = 0,e = n,mid;

    while(s < e)
    {
        mid = (s+e)>>1;
        if(num[mid] == m)
            return mid;
        if(m < num[mid])
            e = mid-1;
        else
            s = mid+1;
    }

    if(s == e)
    {
        if(num[mid] == m)
            return mid;
    }

    return e;
}

int Position_L(LL m,int n)
{
    int s = 0,e = n,mid;

    while(s < e)
    {
        mid = (s+e)>>1;
        if(num[mid] == m)
            return mid;
        if(m < num[mid])
            e = mid-1;
        else
            s = mid+1;
    }

    if(s == e)
    {
        if(num[mid] == m)
            return mid;
    }

    return s;
}

LL Query(int site,int l,int r,int sl,int sr)
{
    if(l == sl && r == sr)
    {
        return st[site];
    }

    int mid = (l+r)>>1;

    if(sr <= mid)
        return Query(site<<1,l,mid,sl,sr);
    if(mid < sl)
        return Query(site<<1|1,mid+1,r,sl,sr);

    return Query(site<<1,l,mid,sl,mid) + Query(site<<1|1,mid+1,r,mid+1,sr);
}


int main()
{
    int i,j;
    LL top = 0;

    memset(mark,0,sizeof(mark));

    for(i = 2;i <= 10000000; ++i)
    {
        if(mark[i] == 0)
        {
            num[top++] = i;
            for(j = i;j <= 10000000; j += i)
            {
                mark[j] = 1;
            }
        }
    }

    //cout<<top<<endl;

    memset(mark,0,sizeof(mark));

    int n;

    scanf("%d",&n);

    for(i = 0;i < n; ++i)
    {
        scanf("%d",&j);
        mark[j]++;
    }

    for(i = 0;i < top; ++i)
    {
        for(ans[i] = 0,j = num[i];j <= 10000000; j += num[i])
        {
            if(mark[j] > 0)
                ans[i] += mark[j];
        }
    }

    Init_St(1,0,top-1);

    int m,sl,sr;

    LL l,r;

    scanf("%d",&m);

    while(m--)
    {
        cin>>l>>r;

        sl = Position_L(l,top-1);
        sr = Position_R(r,top-1);

        if(num[sl] < l)
            sl++;
        if(r < num[sr])
            sr--;

        if(l == r && sl != sr || sl > sr)
        {
            cout<<0<<endl;
        }
        else
        cout<<Query(1,0,top-1,sl,sr)<<endl;
    }
}

activiti源码学习之pvm篇