题意: 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 longusing 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;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
父母养我不容易，我在学校争口气。
