HDU 5317 RGCDQ-白红宇

HDU 5317 RGCDQ

阅读量：4969 次

发布时间：2019-06-12

本文共 1194 字，大约阅读时间需要 3 分钟。

题意：f(i)表示i的质因子个数，给l和r，问在这一区间内f(i)之间任意两个数最大的最大公倍数是多少。

解法：先用筛法筛素数，在这个过程中计算f(i)，因为f(i)不会超过7，所以用一个二维数组统计前i个数中每个f(i)出现的次数，当询问l和r时，用num[r] - num[l - 1]，得到这一区间内的结果，然后讨论一下，如果出现过6和3则答案可能为3，如果出现过4和2则答案可能为2，如果某数字出现两次及以上则答案可能是这个数字，以上几种情况取最大值，即为答案。

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #define LL long longusing namespace std;int f[1000005];int num[1000005][8];void init(){ for(int i = 2; i < 1000005; i++) { if(f[i] == 0) { f[i] = 1; for(int j = i + i; j < 1000005; j += i) f[j]++; } } for(int i = 2; i < 1000005; i++) { memcpy(num[i], num[i - 1], sizeof num[i - 1]); num[i][f[i]]++; }}int main(){ init(); int T; while(~scanf("%d", &T)) { while(T--) { int l, r; scanf("%d%d", &l, &r); int a[8] = {0}; for(int i = 1; i < 8; i++) a[i] = num[r][i] - num[l - 1][i]; int ans = 1; for(int i = 7; i > 0; i--) if(a[i] > 1) { ans = i; break; } if(a[4] && a[2]) ans = max(ans, 2); if(a[6] && a[3]) ans = max(ans, 3); printf("%d\n", ans); } } return 0;}

转载于:https://www.cnblogs.com/Apro/p/4688533.html

你可能感兴趣的文章