hdu 5317 RGCDQ (소수 체 + 전달 방정식)

 
   

     2 2 3 3 5 
   
 
  

 
   

     1 1 
   
 
  

题目大意：

定义：F(x)表示x可以被素因子分解得到的素因子的种类数，给定区间[L,R]，问区间内任意两个F(i)和F(j)之间的最大公约数的最大值为多少。

题目分析：

第一步肯定要先处理出来F(x)函数（肯定是通过素数筛，素因子分解的方法），然后再思考如果每次都在给定区间内暴力寻找，这样的方法肯定会超时。

通过大表和计算发现，由于2*3*5*7*11*13*17*19=9699690>1000000，所以，1000000以内的所有的数的素因子的种类数都小于等于7，所以，我们借助于地推的思想，记sum[i][j] 为从2到i区间内含有j种素因子数的个数，则递推关系为：sum[i][j]=sum[i-1][j]+1;(如果F(j)==j); 或sum[i][j]=sum[i][j-1];(F[j]!=j);

那么区间L到R的含有i个素因子的个数就等于sum[R][i]-sum[L-1][i]个，这样如果存在大于等于两个素因子种类数的个数为一样的值，那么最大的最大公约数就是该值，但是也要考虑一下特殊情况，比如同时有2,4,6（4,6）或者3,6的时候，取一下最大值就行了。

代码实现：

#include 
#include 
#include 
using namespace std;

const int MAXN=1000100;///MAXN          
int prime[MAXN+1];
void getPrime()
{
    memset(prime,0,sizeof(prime));
    for(int i=2;i<=MAXN;i++)
    {
        if(!prime[i])
            prime[++prime[0]]=i;
        for(int j=1;j<=prime[0]&&prime[j]<=MAXN/i;j++)
        {
            prime[prime[j]*i]=1;
            if(i%prime[j]==0)
                break;
        }
    }
}

long long factor[1000100];
int fatCnt;
int getFactors(long long x)
{
    fatCnt=0;
    long long tmp=x;
    for(int i=1;prime[i]<=tmp/prime[i];i++)
    {
        if(tmp%prime[i]==0)
        {
            factor[fatCnt]=prime[i];
            while(tmp%prime[i]==0)
            {
                tmp/=prime[i];
            }
            fatCnt++;
        }
    }
    if(tmp!=1)
    {
        factor[fatCnt++]=tmp;
    }
    return fatCnt;
}

int F[1000010];
int sum[1000010][10];
int main()
{
    int T,L,R;
    getPrime();
    memset(F,0,sizeof(F));
    memset(sum,0,sizeof(sum));
    for(long long i=2;i<=1000000;i++)
    {
        int flag=getFactors(i);
        F[i]=flag;
    }
    for(int i=2;i<=1000000;i++)///        2-i(2<=i<=1000000)   j         
    {
        for(int j=1;j<=7;j++)
        {
            if(F[i]==j)
            {
                sum[i][j]=sum[i-1][j]+1;
            }
            else
            {
                sum[i][j]=sum[i-1][j];
            }
        }
    }
    
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&L,&R);
        int dis[10];
        memset(dis,0,sizeof(dis));
        for(int i=1;i<=7;i++)
        {
            dis[i]=sum[R][i]-sum[L-1][i];
        }
        int ans=1;
        for(int i=7;i>=1;i--)
        {
            if(dis[i]>=2)
            {
                ans=i;
                break;
            }
        }
        if((dis[2]>0) && (dis[4]>0||dis[6]>0))
            ans=max(ans,2);
        if(dis[3]>0 && dis[6]>0)
            ans=max(ans,3);
        if(dis[4]>0 && dis[6]>0)
            ans=max(ans,2);
        printf("%d
",ans);
    }
    return 0;
}