題目連接：戳ME
題意：在一個[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]就是這個區間出現次數>=2次的最大的f[x]。具體看代碼。
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #define clc(a, b) memset(a, b, sizeof(a))
5 using namespace std;
6 const int M = 1e6+5;
7 int dp[M][8];
8 int f[M];
9
10 void Pre() // 預處理函數，
11 {
12 memset( dp, 0, sizeof(dp) );
13 memset( f, 0, sizeof(f) );
14 for( int i = 2; i < M; i++ ) // 首先將f(x)求出來，保存在f[]數組中
15 {
16 if( f[i] )
17 continue;
18 f[i] = 1;
19 for( int j=2; j*i<M; j++ )
20 {
21 f[j*i]++;
22 }
23 }
24 dp[2][1] = 1;
25 for(int i=3; i<M; i++) // 預處理dp[]數組
26 {
27 for(int j=1; j <= 7; j++)
28 {
29 dp[i][j] = dp[i-1][j];
30 }
31 dp[i][f[i]]++;
32 }
33 }
34
35 int main()
36 {
37 Pre();
38 int t;
39 scanf("%d", &t);
40 while( t-- )
41 {
42 int a, b;
43 scanf("%d %d", &a, &b);
44 int ret = 0;
45 for( int i=1; i<8; i++ )
46 { //保證i出現2次 //保證i出現過
47 if( dp[b][i]-dp[a-1][i] > 1 && dp[b][i] )
48 ret = max( ret, i );
49 }
50 printf("%d\n", ret);
51 }
52 }
