2015 Multi

1002 RGCDQ

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

题解

题目大意:定义函数F(x)为x分解为质因数乘积中质因数的个数。对于给定的区间[l,r],求出maxGCD(F(i),F(j))的值。
解题思路:预处理出1000000以内的F(x)可以发现,F(x)的取值是1,2,3,4,5,6,7。而求GCD时,一定是这几个数的组合。那么CGD的结果无非是1,2,3,4,5,6,7。如果我们知道区间[l,r]内,7的值有多少;6的值有多少;5的值有多少;4的值有多少;3的值有多少;2的值有多少;1的值有多少,那么当7的值的个数大于等于2时,结果一定是7;当7的个数小于2,而6的个数大于等于2时,结果一定是6;……………………。因此只要求出区间[l,r]内,1,2,3,4,5,6,7的个数即可,如何求解!!!我们假设s[i][j]的值表示2到i内,F(x)=j(2<=x<=i)的个数,那么区间[l,r]内,7的个数为s[r][7]-s[l-1][7];6的个数为s[r][6]-s[l-1][6];………………,1的个数为s[r][1]-s[l-1][1]。

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
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <fstream>
#include <limits.h>
#define debug "output for debugn"
#define pi (acos(-1.0))
#define eps (1e-4)
#define inf (1<<28)
#define sqr(x) (x) * (x)
#define mod 1e9+7
using namespace std;
typedef long long ll;
typedef unsigned long long ULL;
#define MAX 1000005

//f[i]表示F(X)的值
int f[MAX],s[MAX][8];
//
void ()
{

int i,j;
memset(f,0,sizeof(f));
//利用筛选素数的方法求解f[x]
for(i=2;i<MAX;i++)
{
if(f[i]==0)
{
for(j=i;j<MAX;j=j+i)
{
f[j]++;
}
}
}
//利用递推公式s[i][j]=s[i][j]+s[i-1][j]求解s[i][j]
for(i=2;i<MAX;i++)
{
for(j=1;j<8;j++)
{
s[i][j]=s[i][j]+s[i-1][j];
}
s[i][f[i]]++;
}
}

int main()
{

init();
int i,j,k,l,r,t;
int num[8];
scanf("%d",&t);
while(t--)
{
memset(num,0,sizeof(num));
scanf("%d%d",&l,&r);
for(i=1;i<8;i++)
num[i]=s[r][i]-s[l-1][i];
if(num[7]>=2)
{
printf("7n");
continue;
}
if(num[6]>=2)
{
printf("6n");
continue;
}
if(num[5]>=2)
{
printf("5n");
continue;
}
if(num[4]>=2)
{
printf("4n");
continue;
}
if(num[3]>=2||(num[3]>=1&&num[6]>=1))
{
printf("3n");
continue;
}
if(num[2]>=2||(num[2]>=1&&num[6]>=1)||(num[2]>=1&&num[4]>=1))
{
printf("2n");
continue;
}
printf("1n");
}
return 0;
}

预处理过程中的F(X)的求解利用到了类似筛选素数的方法:
筛选法求素数:
原理:在自然数中标记非素数,剩余的数就是素数(注意1特殊处理了)。
操作:从第一个最小的素数开始,即2,标记它的倍数;找下一个离它最近的并且未被标记的数(该数一定是素数),继续标记该数的倍数。按此继续下去即可标记完所有的非素数。
本题求解F(X):
原理:找出X的质因数的个数。
操作:利用筛选法求素数的操作过程,每当一个数被一个素数标记时,意味着X就有一个素因子,则F(X)的值就加1,换句话说,X被标记的次数就是F(X)的值。(注意标记过程中,质因数本身也要标记,这和筛选法有点不同)。
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
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <fstream>
#include <limits.h>
#define debug "output for debugn"
#define pi (acos(-1.0))
#define eps (1e-4)
#define inf (1<<28)
#define sqr(x) (x) * (x)
#define mod 1e9+7
using namespace std;
typedef long long ll;
typedef unsigned long long ULL;
#define MAX 1000005
int f[MAX];
int main()
{

int i,j,n,x;
memset(f,0,sizeof(f));//初始化
printf("输入区间[2,n]的右端点n(2<n<MAX):n");
scanf("%d",&n);
for(i=2;i<n;i++)//遍历2到n个数,因为这些数可能是素因子
{
if(f[i]==0)//判断是否是素因子
{
for(j=i;j<n;j=j+i)//寻找以i为素因子的数
{
f[j]++;//
}
}
}
printf("输入f[x]的x:");
while(scanf("%d",&x)!=EOF)
{
printf("f[%d]=%dn",x,f[x]);
printf("输入f[x]的x:");
}
return 0;
}