题目连接：Click here
题意：在一个[L,R]内找到最大的gcd(f[i],f[j])其中L<=i<j<=R，f[x]表示i分解质因数后因子的种类数。eg：f[10]=2(10=2*5),f[12]=2(12=2*2*3)。
分析：很容易想到先将f[x]求出来，这里x最大1e6，要在常数时间内求出f[x]。并且稍加分析就知道1<=f[x]<=7,可以用一个dp[i][j]表示从f[1]到f[i]有多少个j。这样就可以在常数时间内预处理出来，后面在O(1)的时间内就可以输出结果。并且这个题并不用把GCD求出来，区间里最大的f[x]就是这个区间f[x]出现次数>=2次的中取最大的f[x]。具体看代码。
#include <iostream>
#include <cstdio>
#include <cstring>
#define clc(a, b) memset(a, b, sizeof(a))
using namespace std;
const int M = 1e6+;
int dp[M][];
int f[M]; void Pre() // 预处理函数，
{
memset( dp, , sizeof(dp) );
memset( f, , sizeof(f) );
for( int i = ; i < M; i++ ) // 首先将f(x)求出来，保存在f[]数组中
{
if( f[i] )
continue;
f[i] = ;
for( int j=; j*i<M; j++ )
{
f[j*i]++;
}
}
dp[][] = ;
for(int i=; i<M; i++) // 预处理dp[]数组
{
for(int j=; j <= ; j++)
{
dp[i][j] = dp[i-][j];
}
dp[i][f[i]]++;
}
} int main()
{
Pre();
int t;
scanf("%d", &t);
while( t-- )
{
int a, b;
scanf("%d %d", &a, &b);
int ret = ;
for( int i=; i<; i++ )
{ //保证i出现2次 //保证i出现过
if( dp[b][i]-dp[a-][i] > && dp[b][i] )
ret = max( ret, i );
}
printf("%d\n", ret);
}
}