nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

转移自老blog

hdu5726

题目难点 :
        给你一个不变的序列，输入很多k，输出区间gcd等于k的区间的数量。

对所有区间计数，枚举左端点，二分右端点即可。
理论依据: 以任意左端点为起点的所有区间的gcd的种类不会超过这个点的值的因子的个数。
细节: 区间询问使用ST表.

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const ll maxn=1e5+5;
map<ll,ll>mp;
ll t,n,q;
ll a[maxn];

ll mm[maxn],rmq[maxn][20];

void st(ll l,ll r){
    mm[0]=-1;
    for(ll i=1;i<maxn;i++){
        mm[i]=((i&i-1)==0)?mm[i-1]+1:mm[i-1];
    }//如果卡常，可以放外面
    for(ll i=l;i<=r;i++)rmq[i][0]=a[i];
    for(ll j=1;j<=mm[r-l+1];j++)
        for(ll i=l;i+(1<<j)-1<=r;i++)
            rmq[i][j]=__gcd(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]);
}
ll query(ll l,ll r){
    ll k=mm[r-l+1];
    return __gcd(rmq[l][k],rmq[r-(1<<k)+1][k]);
}


void ini()
{
    for(ll i=1; i<=n; i++)
    {
        ll l,r=i-1;

       // cout<<i<<":";
       ///100
        while(r<n){//  r : gcd[i..r]!=gcd[i,r+1]
           // cout<<r<<" ";
            ll pre_r=r;
            l=r+2,r=n+1;
            ll gcd=query(i,l-1);
            ///lg
            while(l<r){
                ll mid=(l+r)>>1;
                ///lg
                if(mid>n||gcd!=query(i,mid)){
                    r=mid;// query(i,r)!=gcd
                }
                else l=mid+1;//query(i,l-1)=gcd
            }// query(i,l-1)=gcd&&query(i,l)!=gcd
            mp[gcd]+=(l-1)-(pre_r+1)+1;
            r=l-1;
        }
      //  cout<<endl;
    }

}


int main()
{
    scanf("%lld",&t);
    for(ll time=1; time<=t; time++)
    {
        mp.clear();
        scanf("%lld",&n);
        for(ll i=1;i<=n;i++)scanf("%lld",a+i);

        st(1,n);
        ini();


        scanf("%lld",&q);
        printf("Case #%lld:\n",time);
        for(ll i=1; i<=q; i++)
        {
            ll l,r;
            scanf("%lld %lld",&l,&r);
            ll ans=query(l,r);
            printf("%lld ",ans);
            printf("%lld\n",mp[ans]);
        }
    }
}