题目 http://acm.hdu.edu.cn/showproblem.php?
pid=5317
本题的数据量非常大，測试样例多。数据量大， 所以必须做预处理。也就是用筛法求出全部的F[x]，将全部F[x] 打印出来发现。事实上结果不大，最大的数值是7。所以对于每一个区间询问， 直接暴力求取有多少个 1 2 3 4 5 6 7 就可以，从大到小查找。假设出现2个以上 3-7 的数值，那么最大公约数就是该数字。
假设没有出现两个反复的。那么结果要么是 3 （3,6） 要么是 2 （2，4）。 （4。 6）， （2，6） 。假设都不是。那么就是 1。
我认为本题主要难点在筛法求F[x] 上。
#include <bits/stdc++.h> using namespace std; const int MAX = 1000000+2;
bool vis[MAX];
int f[MAX];
int s[8][MAX]; inline void init() // O(nlngn)
{
// 素数筛法 获取 f(x)
for(int i=2; i<MAX; ++i)
{
if (!vis[i]) // 没有被筛去
{
f[i]++; // 自身是素数，自增 // 筛去i的倍数。 同一时候将f[i的倍数]++。由于i的倍数值，肯定含有i 这个质因子
for(int j=i+i; j<MAX; j+=i)
{
f[j]++;
vis[j] = true; // 筛去
}
}
} // 统计区间 2-i 各有多少个 1 2 3 4 5 6 7
for(int i=2; i<MAX; ++i)
{
for(int j=1; j<=7; ++j)
{
s[j][i] = s[j][i-1]; // 取上一次的结果
if (f[i] == j) // 当前值能够进行累加
s[j][i]++;
}
}
} inline int getMaxGCD(int l, int r)
{
int arr[8] = {};
for(int i=1; i<=7; ++i)
{
arr[i] = s[i][r] - s[i][l-1];
} // 是否有2个以上的情况
for(int i=7; i>2; --i)
{
if (arr[i] >= 2)
return i;
} // 处理单个的情况
if (arr[3]+arr[6] >= 2)
return 3; if (arr[2]+arr[4]+arr[6] >= 2)
return 2; return 1;
} int main(void)
{
//freopen("in.txt", "r", stdin); init(); int t = 0;
scanf("%d", &t);
while(t--)
{
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", getMaxGCD(l, r));
} return 0;
}
另外在杭电上。也有一道类似的题目， 主要考察筛法。
题目 http://acm.hdu.edu.cn/showproblem.php?pid=1215
// 数据量特别大，一定要做预处理 #include <bits/stdc++.h> using namespace std; const int MAX = 500000+2;
int ans[MAX] = {}; inline void init()
{
ans[1] = 1;
for(int i=2; i<MAX; ++i)
{
ans[i]++;
for(int j=i+i; j<MAX; j+=i)
{
ans[j] += i;
}
}
} int main(void)
{
//freopen("in.txt", "r", stdin); init(); int t, n;
cin>>t;
while(t--)
{
scanf("%d", &n);
printf("%d\n", ans[n]);
} return 0;
}
測试用例数量非常大且数据量大的时候。应该做预处理