2015 Multi-University Training Contest 3 1002 RGCDQ

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 592 Accepted Submission(s): 275

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=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 3

3 5

Sample Output

Source

2015 Multi-University Training Contest 3

Recommend

wange2014 | We have carefully selected several similar problems for you: 5326 5325 5324 5323 5322

题意：F(i)代表i这个数的不同素因子的个数，求在给定区间的max GCD(f(i),f(j))

分析：

暴力，先生成区间，再对区间内进行统计

先打表发现1000000之内的数，每个数的不同的素因子个数最多是7个，定义每个数的不同的素因子个数是cnt[i]

那么就可以生成1000000以内的每个数字的不同素因子的个数，用num[i][j]记录前 i 个数字中的有 j 个不同素因子的数字的个数

然后用a[i]记录区间内的有不同的 i 个素因子数字的个数

最后枚举可能的情况就行了

#include<cstdio>
#include<string>
#include<iostream>
#include<cstring>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<stdlib.h>
#include<algorithm>
#define LL __int64
using namespace std;
const int MAXN=1000000+5;
int cnt[MAXN];
int num[MAXN][8];
int a[MAXN];
int kase,st,en;

void init()
{
    for(int i=2;i<=MAXN;i++)
    {
        if(!cnt[i])
        for(int j=i;j<=MAXN;j+=i)
                cnt[j]++;       //统计每个数的不同的素因子个数    
    }

    for(int i=2;i<=MAXN;i++)
    {
        for(int j=1;j<=7;j++)
            num[i][j]=num[i-1][j];
        num[i][cnt[i]]++;        //区间初始化
    }
}

int main()
{
    //freopen("in.txt","r",stdin);
    init();
    cin>>kase;
    while(kase--)
    {
        scanf("%d %d",&st,&en);
        for(int i=1;i<=7;i++)
            a[i]=num[en][i]-num[st-1][i];
        if(a[7]>=2)
        {
            printf("7
");
            continue;
        }
        if(a[6]>=2)
        {
            printf("6
");
            continue;
        }
        if(a[5]>=2)
        {
            printf("5
");
            continue;
        }
        if(a[4]>=2)
        {
            printf("4
");
            continue;
        }
        if(a[3]>=2 || a[3] && a[6]) //如果区间内的3出现两次或者6出现一次的话，输出3
        {
            printf("3
");
            continue;
        }
        if(a[2]>=2 || a[2] && a[4] || a[2] && a[6])
        {
            printf("2
");
            continue;
        }
        printf("1
");
    }
    return 0;
}

View Code

2015 Multi-University Training Contest 3 1002 RGCDQ

相关推荐