F——RGCDQ （HDU 5317）

点击打开链接

Problem Description

Mr. Hdu is interested in Greatest Common Divisor (GCD). He wants to find more and more interesting things about GCD. Today He comes up with Range Greatest Common Divisor Query (RGCDQ). What’s RGCDQ? Please let me explain it to you gradually. For a positive integer x, F(x) indicates the number of kind of prime factor of x. For example F(2)=1. F(10)=2, because 10=2*5. F(12)=2, because 12=2*2*3, there are two kinds of prime factor. For each query, we will get an interval [L, R], Hdu wants to know maxGCD(F(i),F(j))(L≤i<j≤R)

对1~10^6的每个数进行素因子分解，不同素因子的个数作就是它的 f 函数 值，比如12=2^2*3，则f(12)=2，求出它们的 f 函数值之后，给定T组数据，每组数据有一个区间[L,R]，问区间任意两个不同下标的数maxGCD(F(i),F(j)) (L≤i<j≤R)，他们的GCD值最大为多少

解题思路：

首先我们要求一下从 1 - 10^6中对应的 f 函数值，求出函数值之后我们再考虑怎么做，首先观察一下数据范围，10^6*T，肯定会超时，所以我们要想一个 O(1)的算法，我们又观察了一下， 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 > 10^6，所以GCD最大值就是7，也就是说我们可以通过一个DP[i][j] ，表示前 i 个 f 值中有多少个 j,也就是用DP的思想来做这个题（DP并不是很会） ，而这个DP[10^6+5][8]

<span style="font-size:18px;">#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAXN = 1e6+5;
const int INF = 2e9+5;
typedef long long LL;
int f[MAXN];

void Init()
{
    memset(f, 0, sizeof(f));
    for(int i=2; i<MAXN; i++)
    {
        if(!f[i])
        {
            for(int j=i; j<MAXN; j+=i)
                f[j]++;
        }
    }
}

int dp[MAXN][8];
void Pre()
{
    memset(dp, 0, sizeof(dp));
    dp[2][1] = 1;
    for(int i=3; i<MAXN; i++)
    {
        for(int j=1; j<8; j++)
        {
            dp[i][j] = dp[i-1][j];
        }
        dp[i][f[i]]++;
    }
}
int main()
{
    ///cout<<2*3*5*7*11*13*17*19<<endl;
    Init();
    Pre();
    int T, L, R;
    ///cin>>T;
    scanf("%d",&T);
    while(T--)
    {
        int ret = -INF;
        ///cin>>L>>R;
        scanf("%d%d",&L,&R);
        for(int i=1; i<8; i++ )
        {
            if(dp[R][i]-dp[L-1][i]>1 && dp[R][i])
                ret = max(ret, i);
        }
        cout<<ret<<endl;
    }
    return 0;
}</span>