2015年多校联合训练第三场RGCDQ（hdu5317）

本文主要是介绍2015年多校联合训练第三场RGCDQ（hdu5317），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意:
f(i)代表i数中有的素数的种数，给出区间[l,r],求区间内max(gcd(f（i）)),
由于i最大是1e6,2*3*5*7*11*13*17>1e6,故最多不超过7种素数，
先打表打出1e6内的素数种数表，然后用sum[i][j]代表1-i个数中，还有j个素数的个数，最后用sum[r][j] - sum[l-1][j]求出区间内含有j个素数的数的个数，暴力找出1，2，3，4，5，6，7就行

递推公式
sum[i][j] = sum[i-1] + (f[i] == j);

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int MAXN = 1e6;int a[1001005];
int n;
int f[100005];
int sum[MAXN][8];
int flag[10];void init()
{f[1] = 0;for(int i = 2; i <= MAXN; i++){if(!f[i]){f[i]++;for(int j = i*2; j <= MAXN; j += i){f[j]++;}}}for(int i = 2; i <= MAXN; i++)for(int j = 1; j <= 7; j++){sum[i][j] = sum[i-1][j] + (f[i] == j);}}int main()
{
#ifdef xxzfreopen("in.txt","r",stdin);
#endif // xxzint T,L,R;init();scanf("%d",&T);while(T--){scanf("%d%d",&L,&R);int cent[8];for(int i = 1; i <= 7; i++){cent[i] = sum[R][i] - sum[L-1][i];}int ans = 1;for(int i = 7; i >= 1; i--){if(cent[i] >= 2)//如果每个数超过两个，那么gcd后不变{ans = i;break;}}if(cent[2] > 0 && (cent[4] > 0 || cent[6] > 0)) ans = max(ans,2);if(cent[3] > 0 && cent[6] > 0) ans = max(ans,3);if(cent[4] > 0 && cent[6] > 0) ans = max(ans,2);printf("%d\n",ans);}return 0;
}