?

求区间[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;i
      
       1) 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; } 
      
     
    
   
  

?