B-RGCDQ-DU 5317-素数ふるい法

題意f(x)はxが分解できる素数の種類であり、
http://acm.hdu.edu.cn/showproblem.php?pid=5317
まず素数表を打って、更に素数で各数の種類をスクリーニングします
次に任意の区間の要素に対応するf(x)の最大公約数を求めて、----チームメイトはgcdを読み漏らして、区間の最大値を求めるのだと思って、線分の木を撮りました-勉強しません....
答えは明らかに1 2 3 4 5 6 7しかないので…前処理で左端から数字ごとに何個の1 2 3 4 5 6 7があるかをメモしておけば、区間[a,b]に記録されている1 2 3 4 6 7個の数を減算することで、区間の間に何個の1 2 3 4 5があるかを判断することができます
 

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <vector>
#define MAX 1000005
#define inf 0x3f3f3f3f
using namespace std;
#define tree_size MAX*3
int max(int a,int b)
{
	if (a<b)
		return b;
	return a;
};
bool f[1000500]; 
int ans[1000500];  
int yue[1000500][8];  


int main()
{
	
	//      
	__int64 i,j;
	f[1]=true;
	
	for (i=2;i<=MAX;i++)    //1 
	{
		if (f[i]==false)           //  
		{
			for (j=(__int64)i*i;j<=1000500;j=j+i)   //   1  1000  _int64    
			{
				
				f[j]=true;
			}
		}
	} 
	
	
	for (i=2;i<=MAX;i++)    //1 
	{
		if (f[i]==false)
		{	
			for (j=i;j<=MAX;j=j+i)
			{
				ans[j]++;
			} 
		} 
	}
	
	for (i=1;i<=1000000;i++)
	{
		for (j=1;j<=7;j++)
			yue[i][j]=yue[i-1][j];
		yue[i][ans[i]]++;
	}
	
	
	
	int l,t,a,b;
	scanf("%d",&t);
    while(t--)
    {
		
		scanf("%d%d",&a,&b);
		int flag=0;
		for (j=7;j>=3;j--)
		{
			int tmp=yue[b][j]-yue[a-1][j];
			if (tmp>=2)
			{
				printf("%d
",j);
				flag=1;
				break;
			}
		}
		if (flag) continue;
		
		int t1=yue[b][6]-yue[a-1][6];
		int t2=yue[b][3]-yue[a-1][3];
		
		if (t1+t2>=2)  
		{
			printf("3
"); 
			continue;
		}
		else
		{
			t1=yue[b][2]-yue[a-1][2];
			t2=yue[b][4]-yue[a-1][4];
			int t3=yue[b][6]-yue[a-1][6];
			if (t1+t2+t3>=2)
			{ 
				printf("2
");
				continue; 
			}
			else
				printf("1
");
			
		}
			 
	
	
	
}


return 0;

}

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <vector>
#define MAX 1000005
#define inf 0x3f3f3f3f
using namespace std;
#define tree_size MAX*3
int max(int a,int b)
{
	if (a<b)
		return b;
	return a;
};
bool f[1000500]; 
int ans[1000500];  
int yue[1000500][8];  


int main()
{
	
	//      
	__int64 i,j;
	f[1]=true;
	
	for (i=2;i<=MAX;i++)    //1 
	{
		if (f[i]==false)           //  
		{
			for (j=(__int64)i*i;j<=1000500;j=j+i)   //   1  1000  _int64    
			{
				
				f[j]=true;
			}
		}
	} 
	
	
	for (i=2;i<=MAX;i++)    //1 
	{
		if (f[i]==false)
		{	
			for (j=i;j<=MAX;j=j+i)
			{
				ans[j]++;
			} 
		} 
	}
	
	for (i=1;i<=1000000;i++)
	{
		for (j=1;j<=7;j++)
			yue[i][j]=yue[i-1][j];
		yue[i][ans[i]]++;
	}
	
	
	
	int l,t,a,b;
	scanf("%d",&t);
    while(t--)
    {
		
		scanf("%d%d",&a,&b);
		int flag=0;
		for (j=7;j>=3;j--)
		{
			int tmp=yue[b][j]-yue[a-1][j];
			if (tmp>=2)
			{
				printf("%d
",j);
				flag=1;
				break;
			}
		}
		if (flag) continue;
		
		int t1=yue[b][6]-yue[a-1][6];
		int t2=yue[b][3]-yue[a-1][3];
		
		if (t1+t2>=2)  
		{
			printf("3
"); 
			continue;
		}
		else
		{
			t1=yue[b][2]-yue[a-1][2];
			t2=yue[b][4]-yue[a-1][4];
			int t3=yue[b][6]-yue[a-1][6];
			if (t1+t2+t3>=2)
			{ 
				printf("2
");
				continue; 
			}
			else
				printf("1
");
			
		}
			 
	
	
	
}


return 0;

}