解題報告 之 HDU5317 RGCDQ

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 

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 的質因子的種類數，比如20=2*2*5，那麼F(x)=2 。現在給出區間[L,R]，問你該區間内中任意兩個數的GCD的最大值是多少？

分析：首先不管是不是一開始就想到要怎麼做，肯定要完成的是把每個數的F(x)求出來，這裡很自然的想到了篩法。對于每個質數，它的每個倍數的質因子數都++。然後掃一遍之後就完成了F(x)的更新。篩法具體見相關文章一。

好篩完了F(x)，那麼怎麼求最大的GCD呢，一開始發現肯定不能暴力來，是以糾結了一會兒。然後後來看調試發現F(x)的值全都是1，2，3，4。。。這種小數，然後統計出來一看最大的F(x)才隻有7。那麼這個問題就迎刃而解了，直接掃一遍更新到R為止每種F(x)有多少個。然後區間給定之後依次判斷各種情形即可。

上代碼：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

typedef long long ll;
const int MAXN = 1e6 + 10;

int isprime[MAXN];
int f[MAXN];
int dis[MAXN][8];

void ini()
{
	memset( isprime, -1, sizeof isprime );
	memset( f, 0, sizeof f );
	memset( dis, 0, sizeof dis );

	for(int i = 2; i < MAXN; i++)
	{
		if(!isprime[i]) continue;
		for(int j = i; j < MAXN; j += i)
		{
			f[j]++;
			isprime[j] = 0;
		}
	}

	for(int i = 2; i < MAXN; i++)
	{
		for(int j = 1; j <= 7; j++)
		{
			dis[i][j] = dis[i - 1][j];
		}
		dis[i][f[i]]++;
	}

}

int main()
{
	ini();
	int kase;
	scanf( "%d", &kase );

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

		int ma = 0;
		for(int i = 7; i >= 2;i--)
		{
			if(dis[r][i] - dis[l - 1][i] >= 2) 
			{
				ma = i;
				break;
			}
		}

		if(dis[r][6] - dis[l - 1][6] >= 1 && dis[r][2] - dis[l - 1][2] >= 1)
		{
			ma = max( ma, 3 );
		}

		if(dis[r][6] - dis[l - 1][6] >= 1 && dis[r][3] - dis[l - 1][3] >= 1|| dis[r][4] - dis[l - 1][4] >= 1 && dis[r][2] - dis[l - 1][2] >= 1)
		{
			ma = max( ma, 2 );
		}

		ma = max( ma, 1 );
		printf( "%d\n", ma );

	}
	return 0;
}