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

3669 ワード

題意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; }