[原创]HDU 5317 RGCDQ 【筛法+前缀记录】

2016-07-16 19:16:49 Tabris_ 阅读数：164

博客爬取于2020-06-14 22:44:14
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/51925879

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5317

RGCDQ

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2667 Accepted Submission(s): 1060

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=25. F(12)=2, because 12=22*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)

Input
There are multiple queries. In the first line of the input file there is an integer T indicates the number of queries.
In the next T lines, each line contains L, R which is mentioned above.

All input items are integers.
1<= T <= 1000000
2<=L < R<=1000000

Output
For each query，output the answer in a single line.
See the sample for more details.

Sample Input
2
2 3
3 5

Sample Output
1
1

题目大意 ： 就是在1~1e6 这个范围内 f[i]表示i的质因子的种类数 （8=2^3 f[8]=1 ( 仅有2 )） 让你求的是l~r区间内 GCD(F(i),F(j)) (L ≤ i < j ≤ R) 的最大值

题解 ： 这道题目看起来很难 ，其实很好想。首先1~1e6 这个范围内f[i]的最大值也只有7 。举例2357111317=510510 这已经是f[i]=7最小的数了 其次小的就是4849845已经大于1e6 很多了 所以至于f[i]=8的数就不用考虑了

知道了上述这些 就很好处理了 只要预先打表 先用筛法将f[1~1e6]计算出来 在用前缀和的形式 分别吧f[i]=1,=2,…=7的数记录出来 开的数组就是has[1e6][10] 并不会超内存

最后就能记录下来l~r范围内 f[i]=1,=2,…=7 的个数 这样的话再求MAXgcd就方便多了

总时间复杂度就是 O（7e6+7T）

7e6 = nlogn + n

附本题代码

Ps至于最后判断gcd是几的50+代码 是因为写短的 WA了5发 而且是在找不到别的错误 就枚举了一下maxgcd 还好AC了。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <limits.h>
# include <malloc.h>
# include <ctype.h>
# include <math.h>
# include <string>
# include <iostream>
# include <algorithm>
# include <map>
# include <vector>
# include <set>
# include <queue>
# include <time.h>
using namespace std;

/*********************INPUT*************************/
# define s2l(a,b)   scanf("%d%d",&a,&b)
# define s2_l(a,b)  scanf("%I64d%I64d",&a,&b)
# define s1l(a)     scanf("%d",&a)
/*********************OUTPUT*************************/
# define pr1l(a)    printf("%d",a);
# define pr1_l(a)   printf("%I64d",a);
# define pr1ll(a)   printf("%lld",a);
# define space      printf(" ");
# define line       printf("\n");

/*****************type-num***********************/
# define LL long long int
# define _LL __int64
# define LLu unsigned long long int

/****************************************/
# define fr(a,b,c)  for(int a=b;a<c;a++)
# define del(a,b)   memset(b,a,sizeof(b));
# define Rep(a,n)   for(int a=1;a<n;a++)
# define Rop(a,n)   for(int a=1;a<n;a++)

using namespace std;

const int MOD = 1e9+7;
const int Max = 1e6+7;


bool Is_or[Max];
int  f[Max];

void Prime()
{
    memset(Is_or,true,sizeof(Is_or));
    memset(f,0,sizeof(f));

    int n=Max;
    for(int i=2; i<=n; i++)
    {
        if(Is_or[i])
        {
            f[i]++;
            for(int j=i+i; j<=n; j+=i)
            {
                Is_or[j] = false;
                f[j]++;
            }
        }
    }
    return ;
}

int has[Max][8];

void init()
{
    memset(has,0,sizeof(has));

    for(int i=2; i<Max; i++)
    {
        for(int j=1; j<8; j++)
            has[i][j] = has[i-1][j];

        has[i][f[i]]++;
    }
    return ;
}

int main()
{
    Prime();
    init();

    /*
        for(int i=2; i<200; i++)
            printf("%d %d\n",i,f[i]);
    */

    /*
    for(int i=2; i<220; i++)
    {
        for(int j=1; j<8; j++)
            printf("%d ",has[i][j]);
        printf("\n");
    }
    */

    int t;
    scanf("%d",&t);
    while(t--)
    {
        int l,r;
        scanf("%d%d",&l,&r);

        int h[10];
        memset(h,0,sizeof(h));

        for(int i=1; i<8; i++)
            h[i]=has[r][i]-has[l-1][i];

        int flag=1;
        if(h[7]>=2)
        {
            printf("7\n");
            flag=0;
        }

        if(h[6]>=2&&flag)
        {
            printf("6\n");
            flag=0;
        }

        if(h[5]>=2&&flag)
        {
            printf("5\n");
            flag=0;
        }

        if(h[4]&&flag)
        {
            if(h[4]>=2&&flag)
            {
                printf("4\n");
                flag=0;
            }
        }

        if(h[3]&&flag)
        {
            if(h[3]>=2||h[6])
            {
                printf("3\n");
                flag=0;
            }
        }

        if(h[2]&&flag)
        {
            if(h[2]||h[4]||h[6])
            {
                printf("2\n");
                flag=0;
            }
            if(h[4]&&h[6]&&flag)
            {
                printf("2\n");
                flag=0;
            }
        }

        if(flag)
            printf("1\n");
    }
    return 0;
}