2015 HDU 多校联赛 5317 RGCDQ 筛法求解

题目  http://acm.hdu.edu.cn/showproblem.php?

pid=5317

本题的数据量非常大，測试样例多。数据量大， 所以必须做预处理。也就是用筛法求出全部的F[x]，将全部F[x] 打印出来发现。事实上结果不大，最大的数值是7。所以对于每一个区间询问， 直接暴力求取有多少个 1 2 3 4 5 6 7 就可以，从大到小查找。假设出现2个以上 3-7 的数值，那么最大公约数就是该数字。

假设没有出现两个反复的。那么结果要么是 3 （3,6） 要么是 2 （2，4）。 （4。 6）， （2，6） 。假设都不是。那么就是 1。

我认为本题主要难点在筛法求F[x] 上。

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1000000+2;

bool vis[MAX];

int f[MAX];

int s[8][MAX];

inline void init()  // O(nlngn)

{

    // 素数筛法 获取 f(x)

    for(int i=2; i<MAX; ++i)

    {

        if (!vis[i])  // 没有被筛去

        {

            f[i]++; // 自身是素数，自增

            // 筛去i的倍数。 同一时候将f[i的倍数]++。由于i的倍数值，肯定含有i 这个质因子

            for(int j=i+i; j<MAX; j+=i)

            {

                f[j]++;

                vis[j] = true;  // 筛去

            }

        }

    }

    // 统计区间 2-i 各有多少个 1 2 3 4 5 6 7

    for(int i=2; i<MAX; ++i)

    {

        for(int j=1; j<=7; ++j)

        {

            s[j][i] = s[j][i-1];    // 取上一次的结果

            if (f[i] == j)  // 当前值能够进行累加

                s[j][i]++;

        }

    }

}

inline int getMaxGCD(int l, int r)

{

    int arr[8] = {};

    for(int i=1; i<=7; ++i)

    {

        arr[i] = s[i][r] - s[i][l-1];

    }

    // 是否有2个以上的情况

    for(int i=7; i>2; --i)

    {

        if (arr[i] >= 2)

            return i;

    }

    // 处理单个的情况

    if (arr[3]+arr[6] >= 2)

        return 3;

    if (arr[2]+arr[4]+arr[6] >= 2)

        return 2;

    return 1;

}

int main(void)

{

    //freopen("in.txt", "r", stdin);

    init();

    int t = 0;

    scanf("%d", &t);

    while(t--)

    {

        int l, r;

        scanf("%d%d", &l, &r);

        printf("%d\n", getMaxGCD(l, r));

    }

    return 0;

}

另外在杭电上。也有一道类似的题目， 主要考察筛法。

题目  http://acm.hdu.edu.cn/showproblem.php?pid=1215

// 数据量特别大，一定要做预处理

#include <bits/stdc++.h>

using namespace std;

const int MAX = 500000+2;

int ans[MAX] = {};

inline void init()

{

    ans[1] = 1;

    for(int i=2; i<MAX; ++i)

    {

        ans[i]++;

        for(int j=i+i; j<MAX; j+=i)

        {

            ans[j] += i;

        }

    }

}

int main(void)

{

    //freopen("in.txt", "r", stdin);

    init();

    int t, n;

    cin>>t;

    while(t--)

    {

        scanf("%d", &n);

        printf("%d\n", ans[n]);

    }

    return 0;

}

測试用例数量非常大且数据量大的时候。应该做预处理