题目链接：

pid=5317" target="_blank">http://acm.hdu.edu.cn/showproblem.php?pid=5317

2

2 3

3 5

1

1

题意：

一个函数 ：f(x)它的值是x的素因子不同的个数；

如：f(2) = 1, f(3) = 1。

当中(L<=i<j<=R),即区间内随意不相等的两个数的最大公约数的最大值；

PS:

由于2*3*5*7*11*13*17 > 1e6！

所以f(x)的值最大为7;

我们先打表求出每一个f(x)的值；

//int s[maxn][10];//前i个F中j的个数

然后再利用前缀和s[r][i] - s[l-1][i]。

求出区间[l, r]的值。

代码例如以下：

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

using namespace std;

#define maxn 1000000+7

int prim[maxn];

int s[maxn][10];//前i个F中j的个数

int GCD(int a, int b)

{

    if(b==0)

        return a;

    return GCD(b, a%b);

}

void init()

{

    memset(prim, 0, sizeof(prim));

    memset(s, 0, sizeof(s));

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

    {

        if(prim[i]) continue;

        prim[i] = 1;

        for(int j = 2; j * i < maxn; j++)

        {

            prim[j*i]++;//不同素数个数

        }

    }

    s[2][1] = 1;

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

    {

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

        {

            s[i][j] = s[i-1][j];

        }

        s[i][prim[i]]++;

    }

}

int main()

{

    int t;

    int l, r;

    init();

    scanf("%d",&t);

    while(t--)

    {

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

        int c[17];

        int k = 0;

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

        {

            int tt = s[r][i] - s[l-1][i];

            if(tt >= 2)//超过两个以上记为2个就可以

            {

                c[k++] = i;

                c[k++] = i;

            }

            else if(tt == 1)

            {

                c[k++] = i;

            }

        }

        int maxx = 1;

        for(int i = 0; i < k-1; i++)

        {

            for(int j = i+1; j < k; j++)

            {

                int tt = GCD(c[i],c[j]);

                maxx = max(maxx, tt);

            }

        }

        printf("%d\n",maxx);

    }

    return 0;

}