MYF

HDU 5317 RGCDQ

Posted on | In | | Visitors

题目链接

HDU 5317

解题方法：先用筛法算出每个数的质因子个数，然后统计。

题目分析

题目大意

对于任意一个数字x，定义一个函数F(x)，表示x的质因子个数。对于一个闭区间[l,r]，其中每一个数都用F(x)表示，形成长度为r-l+1的数组b，问数组b中任意两个数都存在一个最大公约数，问这个区间内最大的最大公约数是多少？

解析

因为要对每一个数字x，找到该数对应的F(x)，所以采用筛法求质数的方法进行标记。然后可以发现，在数据范围内，一个数最多只有7个质因子，所以可以暴力的去搞，但是要进行1000000次询问，每次询问要跑r-l+1个数，这样会很慢，交了之后会T掉。找最大公约数，实际上就是找区间中出现频率大于等于2的那个数。采取使用时间换取空间的方式，用vis[maxn][8]来记录从2到当前i（含）总共含有的1,2,3,4,5,6,7的数字数量，给定一个区间[l,r]时只需要扫v=vis[r][i]-vis[l-1][i], i∈[1,7]即可知道[l,r]区间内每个数出现的次数，大大降低了时间复杂度，最后一个v>=2的i即为答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define rt(n)       (j == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#define eps 1e-8
#define INF 0x3f3f3f3f
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
#define maxn 1000005
#define mod 1000000007
int num[maxn];
int vis[maxn][8];
void init()
{
    for(int i=2; i<maxn; i++)
    {
        if(num[i]==0)
        {
            for(int j=i; j<maxn; j+=i)
            {
                num[j]++;
            }
        }
        for(int j=1;j<=7;j++)
        {
            if(num[i]%j==0)
                vis[i][j]=vis[i-1][j]+1;
            else
                vis[i][j]=vis[i-1][j];
        }
    }
}
int main()
{
    init();
    int t,v,l,r;
    scanf("%d",&t);
    while(t--)
    {
        int ans=0;
        scanf("%d %d",&l,&r);
        for(int i=1; i<=7; i++)
        {
            v=vis[r][i]-vis[l-1][i];
            if(v>=2) ans=i;
        }
        printf("%d\n",ans);
    }
    return 0;
}