HDU 5317 RGCDQ (素因子分解+預處理)

HDU 5317 RGCDQ (素因子分解+預處理)

求區間[l,r]所有數的素因子的種類的最大的最大公約數。。。額，不知道怎麼描述了。。。

比如說區間內的所有數的素因子種類分別為1,2,3,4,5,6,7那麼結果就是gcd(3,6)

分析：

數據的范圍是1~1000000,因子數最大為7，我們首先要預處理出所有數的數的因子數，但是因為

數據的范圍比較大我們不能直接暴力求結果，因為因子數的可能取值比較小，因此我們可以預處

理出每種取值數的前綴和，然後就可以在O(1)的的時間內求出區間內每種取值的數。

代碼如下：

#include 
#include 
#include 
#include 
using namespace std;

const int maxn = 1e3+10;

int pri[maxn],cnt;
bool vis[maxn];
void getprime(){
    cnt=0;
    memset(vis,0,sizeof(vis));
    for(int i=2;i1) num[i]++;
        ff=max(num[i],ff);
    }
    sum[0][0]=0;sum[0][1]=0;sum[0][2]=0;sum[0][3]=0;
    sum[0][4]=0;sum[0][5]=0;sum[0][6]=0;sum[0][7]=0;
    for(int i=1;i<1000001;i++){
        for(int j=1;j<=7;j++)
           sum[i][j]=sum[i-1][j];
        sum[i][num[i]]++;
    }
}

int a[10];

int main()
{
    init();
    int t,l,r;
    scanf(%d,&t);
    while(t--){
        scanf(%d%d,&l,&r);
        int tag = 0;
        for(int i=7;i>=1;i--)
            a[i]=sum[r][i]-sum[l-1][i];
        for(int i=7;i>=3;i--){
            if(a[i]>=2){
                tag = i;
                break;
            }
        }
        if(tag){
            printf(%d
,tag);
        }
        else{
            if(a[3]>=1&&a[6]>=1){
                puts(3);
                continue;
            }
            else if((a[2]>=1&&a[4]>=1)||a[2]>=2){
                puts(2);
                continue;
            }
            else puts(1);
        }
    }
    return 0;
}