热身训练2 GCD

简要题意：

n个数字，a1,a2,...,an

m次询问(l,r)，每次询问需回答 1.gcd(al,al+1,al+2,...,ar);2.gcd(ax,ax+1,ax+2,...,ay)=gcd(al,al+1,al+2,...,ar)的个数(x<=y)。

分析：

算第一个询问，由于a数组是静态的，我们可以用ST表来预处理。

对于第二个询问，我们先令左端点x固定，那么随着y的增加，gcd(ax,...,ay)会越来越小，这是可以二分的！！！

这样看来，我们完全可以预处理出每个gcd所有的个数！！！

#include<bits/stdc++.h>

using namespace std;

#define re register int

#define LL long long

const int N=1e5+5;

int gcd(const int a, const int b)

{

    if(b == 0) return a;

    return gcd(b, a%b);

}

int f[N][30], lg[N], n;

inline void ST_init()

{

    for(re i=1;i<=20;++i)

        for(re j=1;j+(1<<i)-1 <= n; ++j)

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

}

inline int gtgcd(const int x, const int y)

{

    int k=lg[y-x+1];

    return gcd(f[x][k], f[y-(1<<k)+1][k]);

}

inline void work()

{

    scanf("%d",&n);

    for(re i=1;i<=n;++i) scanf("%d",&f[i][0]);

    ST_init();

    map<int, long long>mp;

    for(re i=1;i<=n;++i)

    {

        int p=i, tmp = f[i][0];

        while(p <= n)

        {

            int ret=-1, L=p, R=n;

            while(L <= R)

            {

                int mid=(L+R)>>1;

                if(gtgcd(i, mid) == tmp) ret=mid, L=mid+1;

                else R=mid-1;

            }

            mp[tmp] += ret-p+1;

            p = ret+1;

            tmp = gtgcd(i, p);

        }

    }

    int m; scanf("%d",&m);

    while(m--)

    {

        int x, y, g;

        scanf("%d%d",&x,&y);

        g = gtgcd(x, y);

        printf("%d %lld\n", g, mp[g]);

    }

}

signed main()

{

    for(re i=2;i<=100000;++i) lg[i] = lg[i>>1]+1;

    int T; scanf("%d",&T);

    for(re i=1;i<=T;++i)

    {

        printf("Case #%d:\n", i);

        work();

    }

    return 0;

}

巴特西

热身训练2 GCD

最新文章

热门文章