HDU 5726 GCD （2016 Multi-University Training Contest 1）

Time Limit: 5000MS

Memory Limit: 65536KB

64bit IO Format: %I64d & %I64u

Description

Give you a sequence of

Input

The first line of input contains a number

Output

For each case, you need to output “Case #:t” at the beginning.(with quotes,

Sample Input

Sample Output

Case #1:
8
4
4
1 

Source

2016 Multi-University Training Contest 1

题意：给一个数组a，大小为n，接下来有m个询问，每次询问给出l、r，定义f[l,r]=gcd（al，al+1，...，ar），问f[l,r]的值和有多少对（l'，r'）使得f[l',r']=f[l,r]。1<=l<=r<=n，题目中给的数据过大，不可直接使用dp方程。

思路：

　　第一步，RMQ预处理一下，定义f[i][j]为：ai开始，连续2^j个数的最大公约数，所以f[1][0]=a[1],f[1][1]=gcd(a1,a2),f[1][2]=gcd(a1,a2,a3,a4)。递推即可。

　　递推公式如下：

　　1. f[i][0]=a[i];

　　2. f[i][j]=gcd(f[i][j-1],f[i+(1<<(j-1))][j-1])

　　接着查询时就只需O(1)时间，如下：

　　令k=log2(r-l+1)，RMQ(l,r)=gcd(f[l][k],f[r-(1<<k)+1][k]);

　　注：f[l][k] 和 f[r-(1<<k)+1][k]可能会有重叠，但不影响最终的gcd值。

　　第二步二分法：我们可以枚举左端点 i 从1-n，对每个i，二分右端点，计算每种gcd值的数量，因为如果左端点固定，gcd值随着右端点的往右，呈现单调不增，这点很重要，比赛时没有想到，而且gcd值每次变化，至少除以2，所以gcd的数量为nlog2(n)种，可以开map<int,long long>存每种gcd值的数量，注意n大小为10万，所以有可能爆int。

#include<stdio.h>
#include<math.h>
#include<map>
using namespace std;
int f[100010][18];
int a[100010];
int n,m;
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
void rmq()
{
    for(int i=1; i<=n; i++) f[i][0]=a[i];
    for(int j=1; (1<<j)<=n; j++)
    {
        for(int i=1; i+(1<<j)-1<=n; i++)
        {
            f[i][j]=gcd(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
}
int RMQ(int l,int r)
{
    int k=0;
    while((1<<(k+1))<=r-l+1) k++;
    return gcd(f[l][k],f[r-(1<<k)+1][k]);
}
map<int,long long> mp;
void setTable()
{
    mp.clear();
    for(int i=1; i<=n; i++)
    {
        int g=f[i][0],j=i;
        while(j<=n)
        {
            int l=j,r=n;
            while(l<r)
            {
                int mid=(l+r+1)>>1;
                if(RMQ(i,mid)==g) l=mid;
                else r=mid-1;
            }
            mp[g]+=l-j+1;
            j=l+1;
            g=RMQ(i,j);
        }
    }
}
int main()
{
    int t,l,r;
    int cas=1;
    scanf("%d",&t);
    while(t--)
    {
        printf("Case #%d:
",cas++);
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
        }
        rmq();
        setTable();
        scanf("%d",&m);
        for(int i=0; i<m; i++)
        {
            scanf("%d%d",&l,&r);
            int g=RMQ(l,r);
            printf("%d %I64d
",g,mp[g]);
        }
    }
    return 0;
}

View Code

HDU 5726 GCD （2016 Multi-University Training Contest 1）

相关推荐